1use serde::Deserialize;
2use sha2::{Digest, Sha256};
3
4use crate::error::{QecError, Result};
5use crate::family_contract::verify_css_orthogonality;
6use crate::finite_group::{
7 FiniteGroupSpec, GroupAlgebraElement, left_regular_lift, right_regular_lift,
8};
9use crate::regular_classical::{SplitMix64V1, bounded_index_v1};
10
11pub const RANDOM_TWO_BLOCK_ALGORITHM_V1: u32 = 1;
12
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct RandomTwoBlockSpec {
15 pub group: FiniteGroupSpec,
16 pub support_a_weight: usize,
17 pub support_b_weight: usize,
18 pub seed: u64,
19 pub algorithm_version: u32,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct RandomTwoBlockCssChecks {
24 pub num_cols: usize,
25 pub h_x: Vec<Vec<usize>>,
26 pub h_z: Vec<Vec<usize>>,
27 pub support_a: Vec<usize>,
28 pub support_b: Vec<usize>,
29 pub metadata: RandomTwoBlockMetadata,
30}
31
32#[derive(Debug, Clone, PartialEq, Eq)]
33pub struct RandomTwoBlockMetadata {
34 pub group_digest: String,
35 pub seed: u64,
36 pub support_a_weight: usize,
37 pub support_b_weight: usize,
38 pub algorithm_version: u32,
39}
40
41#[derive(Debug, Deserialize)]
42struct RandomTwoBlockSpecJson {
43 group: ExplicitRandomTwoBlockGroupJson,
44 support_a_weight: usize,
45 support_b_weight: usize,
46 seed: Option<u64>,
47 algorithm_version: u32,
48}
49
50#[derive(Debug, Deserialize)]
51struct ExplicitRandomTwoBlockGroupJson {
52 name: Option<String>,
53 element_order: Option<String>,
54 order: usize,
55 identity: usize,
56 multiplication_table: Vec<Vec<usize>>,
57}
58
59impl RandomTwoBlockSpec {
60 pub fn new(
61 group: FiniteGroupSpec,
62 support_a_weight: usize,
63 support_b_weight: usize,
64 seed: u64,
65 algorithm_version: u32,
66 ) -> Result<Self> {
67 let spec = Self {
68 group,
69 support_a_weight,
70 support_b_weight,
71 seed,
72 algorithm_version,
73 };
74 verify_random_two_block_spec(&spec)?;
75 Ok(spec)
76 }
77}
78
79pub fn random_two_block_spec_from_json_str(input: &str) -> Result<RandomTwoBlockSpec> {
80 let parsed: RandomTwoBlockSpecJson = serde_json::from_str(input)
81 .map_err(|error| QecError::InvalidCssConstructionJson(error.to_string()))?;
82 let seed = parsed
83 .seed
84 .ok_or_else(|| QecError::InvalidRandomTwoBlockSpec {
85 option: "seed",
86 reason: "must be provided".to_owned(),
87 })?;
88 let ExplicitRandomTwoBlockGroupJson {
89 name,
90 element_order,
91 order,
92 identity,
93 multiplication_table,
94 } = parsed.group;
95 let _ = (name, element_order);
96 let group = FiniteGroupSpec::new(order, identity, multiplication_table)?;
97 RandomTwoBlockSpec::new(
98 group,
99 parsed.support_a_weight,
100 parsed.support_b_weight,
101 seed,
102 parsed.algorithm_version,
103 )
104}
105
106pub fn random_two_block_css_checks(spec: &RandomTwoBlockSpec) -> Result<RandomTwoBlockCssChecks> {
107 verify_random_two_block_spec(spec)?;
108
109 let mut stream = SplitMix64V1::new(spec.seed);
110 let support_a = sample_support_v1(&mut stream, spec.group.order(), spec.support_a_weight);
111 let support_b = sample_support_v1(&mut stream, spec.group.order(), spec.support_b_weight);
112 let a = GroupAlgebraElement::new(&spec.group, support_a.clone())?;
113 let b = GroupAlgebraElement::new(&spec.group, support_b.clone())?;
114 let left_a = left_regular_lift(&spec.group, &[vec![a]])?;
115 let right_b = right_regular_lift(&spec.group, &[vec![b]])?;
116 let h_x = left_a.hconcat(&right_b)?;
117 let h_z = right_b.transpose()?.hconcat(&left_a.transpose()?)?;
118
119 verify_css_orthogonality(h_x.num_cols(), h_x.rows(), h_z.rows())?;
120
121 Ok(RandomTwoBlockCssChecks {
122 num_cols: h_x.num_cols(),
123 h_x: h_x.rows().to_vec(),
124 h_z: h_z.rows().to_vec(),
125 support_a,
126 support_b,
127 metadata: RandomTwoBlockMetadata {
128 group_digest: group_digest(&spec.group),
129 seed: spec.seed,
130 support_a_weight: spec.support_a_weight,
131 support_b_weight: spec.support_b_weight,
132 algorithm_version: spec.algorithm_version,
133 },
134 })
135}
136
137fn sample_support_v1(stream: &mut SplitMix64V1, order: usize, weight: usize) -> Vec<usize> {
138 let mut pool = (0..order).collect::<Vec<_>>();
139 for i in 0..weight {
140 let offset = bounded_index_v1(stream, (order - i) as u64)
141 .expect("sampling support from nonempty candidates");
142 let j = i + offset as usize;
143 pool.swap(i, j);
144 }
145 pool[..weight].sort_unstable();
146 pool.truncate(weight);
147 pool
148}
149
150fn verify_random_two_block_spec(spec: &RandomTwoBlockSpec) -> Result<()> {
151 if spec.algorithm_version != RANDOM_TWO_BLOCK_ALGORITHM_V1 {
152 return Err(QecError::UnsupportedRandomTwoBlockAlgorithm {
153 algorithm_version: spec.algorithm_version,
154 });
155 }
156 verify_support_weight(
157 spec.support_a_weight,
158 spec.group.order(),
159 "support_a_weight",
160 )?;
161 verify_support_weight(
162 spec.support_b_weight,
163 spec.group.order(),
164 "support_b_weight",
165 )
166}
167
168fn verify_support_weight(weight: usize, order: usize, option: &'static str) -> Result<()> {
169 if weight == 0 {
170 return Err(QecError::InvalidRandomTwoBlockSpec {
171 option,
172 reason: "must be greater than zero".to_owned(),
173 });
174 }
175 if weight > order {
176 return Err(QecError::InvalidRandomTwoBlockSpec {
177 option,
178 reason: "must be at most the group order".to_owned(),
179 });
180 }
181 Ok(())
182}
183
184fn group_digest(group: &FiniteGroupSpec) -> String {
185 format!(
186 "sha256:{}",
187 lower_hex(Sha256::digest(group.to_json_string()))
188 )
189}
190
191fn lower_hex(bytes: impl AsRef<[u8]>) -> String {
192 const HEX: &[u8; 16] = b"0123456789abcdef";
193 let bytes = bytes.as_ref();
194 let mut output = String::with_capacity(bytes.len() * 2);
195 for &byte in bytes {
196 output.push(HEX[(byte >> 4) as usize] as char);
197 output.push(HEX[(byte & 0x0f) as usize] as char);
198 }
199 output
200}