ergotree_interpreter/sigma_protocol/
sig_serializer.rs

1//! Serialization of proof tree signatures
2
3use std::convert::TryInto;
4
5use super::gf2_192::gf2_192poly_from_byte_array;
6use super::prover::ProofBytes;
7use super::unchecked_tree::UncheckedConjecture;
8use super::unchecked_tree::UncheckedLeaf;
9use super::unchecked_tree::UncheckedTree;
10use super::wscalar::Wscalar;
11use super::GROUP_SIZE;
12use super::SOUNDNESS_BYTES;
13use crate::sigma_protocol::dht_protocol::SecondDhTupleProverMessage;
14use crate::sigma_protocol::unchecked_tree::UncheckedDhTuple;
15use crate::sigma_protocol::Challenge;
16use crate::sigma_protocol::GroupSizedBytes;
17use crate::sigma_protocol::UncheckedSchnorr;
18
19use ergotree_ir::serialization::sigma_byte_reader;
20use ergotree_ir::serialization::sigma_byte_reader::SigmaByteRead;
21use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWrite;
22use ergotree_ir::serialization::sigma_byte_writer::SigmaByteWriter;
23use ergotree_ir::serialization::SigmaSerializationError;
24use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
25use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
26use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
27
28use gf2_192::Gf2_192Error;
29use thiserror::Error;
30
31/// Recursively traverses the given node and serializes challenges and prover messages to the given writer.
32/// Note, sigma propositions and commitments are not serialized.
33/// Returns the proof bytes containing all the serialized challenges and prover messages (aka `z` values)
34pub(crate) fn serialize_sig(tree: UncheckedTree) -> ProofBytes {
35    let mut data = Vec::with_capacity(SOUNDNESS_BYTES + GROUP_SIZE);
36    let mut w = SigmaByteWriter::new(&mut data, None);
37    #[allow(clippy::unwrap_used)]
38    // since serialization may fail only for underlying IO errors (OOM, etc.) it's ok to force unwrap
39    sig_write_bytes(&tree, &mut w, true).unwrap();
40    ProofBytes::Some(data)
41}
42
43/// Recursively traverses the given node and serializes challenges and prover messages to the given writer.
44/// Note, sigma propositions and commitments are not serialized.
45/// Returns the proof bytes containing all the serialized challenges and prover messages (aka `z` values)
46fn sig_write_bytes<W: SigmaByteWrite>(
47    node: &UncheckedTree,
48    w: &mut W,
49    write_challenges: bool,
50) -> Result<(), std::io::Error> {
51    if write_challenges {
52        node.challenge().sigma_serialize(w)?;
53    }
54    match node {
55        UncheckedTree::UncheckedLeaf(leaf) => match leaf {
56            UncheckedLeaf::UncheckedSchnorr(us) => {
57                let mut sm_bytes = us.second_message.z.as_scalar_ref().to_bytes();
58                w.write_all(sm_bytes.as_mut_slice())?;
59                Ok(())
60            }
61            UncheckedLeaf::UncheckedDhTuple(dh) => {
62                let mut sm_bytes = dh.second_message.z.as_scalar_ref().to_bytes();
63                w.write_all(sm_bytes.as_mut_slice())
64            }
65        },
66        UncheckedTree::UncheckedConjecture(conj) => match conj {
67            UncheckedConjecture::CandUnchecked {
68                challenge: _,
69                children,
70            } => {
71                // don't write children's challenges -- they are equal to the challenge of this node
72                for child in children {
73                    sig_write_bytes(child, w, false)?;
74                }
75                Ok(())
76            }
77            UncheckedConjecture::CorUnchecked {
78                challenge: _,
79                children,
80            } => {
81                // don't write last child's challenge -- it's computed by the verifier via XOR
82                let (last, elements) = children.split_last();
83                for child in elements {
84                    sig_write_bytes(child, w, true)?;
85                }
86                sig_write_bytes(last, w, false)?;
87                Ok(())
88            }
89            UncheckedConjecture::CthresholdUnchecked {
90                challenge: _,
91                children,
92                k,
93                polynomial,
94            } => {
95                let mut polynomial_bytes = polynomial.to_bytes();
96                assert_eq!(
97                    polynomial_bytes.len(),
98                    (children.len() - *k as usize) * SOUNDNESS_BYTES
99                );
100                // write the polynomial, except the zero-degree coefficient
101                w.write_all(polynomial_bytes.as_mut_slice())?;
102                for child in children {
103                    sig_write_bytes(child, w, false)?;
104                }
105                Ok(())
106            }
107        },
108    }
109}
110
111/// Verifier Step 2: In a top-down traversal of the tree, obtain the challenges for the children of every
112/// non-leaf node by reading them from the proof or computing them.
113/// Verifier Step 3: For every leaf node, read the response z provided in the proof.
114/// * `exp` - sigma proposition which defines the structure of bytes from the reader
115/// * `proof` - proof to extract challenges from
116pub fn parse_sig_compute_challenges(
117    exp: &SigmaBoolean,
118    mut proof_bytes: Vec<u8>,
119) -> Result<UncheckedTree, SigParsingError> {
120    if proof_bytes.is_empty() {
121        return Err(SigParsingError::EmptyProof(exp.clone()));
122    }
123    let mut r = sigma_byte_reader::from_bytes(proof_bytes.as_mut_slice());
124    parse_sig_compute_challenges_reader(exp, &mut r, None)
125        .map_err(|e| SigParsingError::TopLevelExpWrap(e.into(), exp.clone()))
126}
127
128/// Verifier Step 2: In a top-down traversal of the tree, obtain the challenges for the children of every
129/// non-leaf node by reading them from the proof or computing them.
130/// Verifier Step 3: For every leaf node, read the response z provided in the proof.
131/// * `exp` - sigma proposition which defines the structure of bytes from the reader
132fn parse_sig_compute_challenges_reader<R: SigmaByteRead>(
133    exp: &SigmaBoolean,
134    r: &mut R,
135    challenge_opt: Option<Challenge>,
136) -> Result<UncheckedTree, SigParsingError> {
137    // Verifier Step 2: Let e_0 be the challenge in the node here (e_0 is called "challenge" in the code)
138    let challenge = if let Some(c) = challenge_opt {
139        c
140    } else {
141        Challenge::sigma_parse(r).map_err(|_| SigParsingError::ChallengeRead(exp.clone()))?
142    };
143
144    match exp {
145        SigmaBoolean::TrivialProp(b) => Err(SigParsingError::TrivialPropFound(*b)),
146        SigmaBoolean::ProofOfKnowledge(tree) => match tree {
147            SigmaProofOfKnowledgeTree::ProveDlog(dl) => {
148                // Verifier Step 3: For every leaf node, read the response z provided in the proof.
149                let z = read_scalar(r)
150                    .map_err(|_| SigParsingError::ScalarReadProveDlog(exp.clone()))?;
151                Ok(UncheckedSchnorr {
152                    proposition: dl.clone(),
153                    commitment_opt: None,
154                    challenge,
155                    second_message: z.into(),
156                }
157                .into())
158            }
159            SigmaProofOfKnowledgeTree::ProveDhTuple(dh) => {
160                // Verifier Step 3: For every leaf node, read the response z provided in the proof.
161                let z = read_scalar(r)
162                    .map_err(|_| SigParsingError::ScalarReadProveDhTuple(exp.clone()))?;
163                Ok(UncheckedDhTuple {
164                    proposition: dh.clone(),
165                    commitment_opt: None,
166                    challenge,
167                    second_message: SecondDhTupleProverMessage { z },
168                }
169                .into())
170            }
171        },
172        SigmaBoolean::SigmaConjecture(conj) => match conj {
173            SigmaConjecture::Cand(cand) => {
174                // Verifier Step 2: If the node is AND, then all of its children get e_0 as
175                // the challenge
176                let children = cand.items.try_mapped_ref(|it| {
177                    parse_sig_compute_challenges_reader(it, r, Some(challenge.clone()))
178                })?;
179                Ok(UncheckedConjecture::CandUnchecked {
180                    challenge,
181                    children,
182                }
183                .into())
184            }
185            SigmaConjecture::Cor(cor) => {
186                // Verifier Step 2: If the node is OR, then each of its children except rightmost
187                // one gets the challenge given in the proof for that node.
188                // The rightmost child gets a challenge computed as an XOR of the challenges of all the other children and e_0.
189
190                // Read all the children but the last and compute the XOR of all the challenges including e_0
191                let mut children: Vec<UncheckedTree> = Vec::with_capacity(cor.items.len());
192
193                let (last, rest) = cor.items.split_last();
194                for it in rest {
195                    children.push(parse_sig_compute_challenges_reader(it, r, None)?);
196                }
197                let xored_challenge = children
198                    .clone()
199                    .into_iter()
200                    .map(|c| c.challenge())
201                    .fold(challenge.clone(), |acc, c| acc.xor(c));
202                let last_child =
203                    parse_sig_compute_challenges_reader(last, r, Some(xored_challenge))?;
204                children.push(last_child);
205
206                #[allow(clippy::unwrap_used)] // since quantity is preserved unwrap is safe here
207                Ok(UncheckedConjecture::CorUnchecked {
208                    challenge,
209                    children: children.try_into().unwrap(),
210                }
211                .into())
212            }
213            SigmaConjecture::Cthreshold(ct) => {
214                // Verifier Step 2: If the node is THRESHOLD,
215                // evaluate the polynomial Q(x) at points 1, 2, ..., n to get challenges for child 1, 2, ..., n, respectively.
216                // Read the polynomial -- it has n-k coefficients
217                let n_children = ct.children.len();
218                let n_coeff = n_children - ct.k as usize;
219                let buf_size = n_coeff * SOUNDNESS_BYTES;
220                let mut coeff_bytes = vec![0u8; buf_size];
221                r.read_exact(&mut coeff_bytes)
222                    .map_err(|_| SigParsingError::CthresholdCoeffRead(exp.clone()))?;
223                let polynomial = gf2_192poly_from_byte_array(challenge.clone(), coeff_bytes)?;
224
225                let children =
226                    ct.children
227                        .clone()
228                        .enumerated()
229                        .try_mapped_ref(|(idx, child)| {
230                            // Note the cast to `u8` is safe since `ct.children` is of type
231                            // `SigmaConjectureItems<_>` which is a `BoundedVec<_, 2, 255>`.
232                            let one_based_index = (idx + 1) as u8;
233                            let ch = polynomial.evaluate(one_based_index).into();
234                            parse_sig_compute_challenges_reader(child, r, Some(ch))
235                        })?;
236                Ok(UncheckedConjecture::CthresholdUnchecked {
237                    challenge,
238                    children,
239                    k: ct.k,
240                    polynomial,
241                }
242                .into())
243            }
244        },
245    }
246}
247
248fn read_scalar<R: SigmaByteRead>(r: &mut R) -> Result<Wscalar, SigmaSerializationError> {
249    let mut scalar_bytes: Box<[u8; super::GROUP_SIZE]> = Box::new([0; super::GROUP_SIZE]);
250    let bytes_read = r.read(&mut *scalar_bytes)?;
251    scalar_bytes.rotate_right(super::GROUP_SIZE - bytes_read);
252    Ok(Wscalar::from(GroupSizedBytes(scalar_bytes)))
253}
254
255/// Errors when parsing proof tree signatures
256#[allow(missing_docs)]
257#[derive(Error, PartialEq, Debug, Clone)]
258pub enum SigParsingError {
259    #[error("Empty proof for exp: {0:?}")]
260    EmptyProof(SigmaBoolean),
261
262    #[error("Unexpected TrivialProp found: {0}")]
263    TrivialPropFound(bool),
264
265    #[error("gf2_192 error: {0}")]
266    Gf2_192Error(#[from] Gf2_192Error),
267
268    #[error("Empty commitment in UncheckedLeaf with proposition: {0:?}")]
269    EmptyCommitment(SigmaBoolean),
270
271    #[error("Challenge reading erorr with exp: {0:?}")]
272    ChallengeRead(SigmaBoolean),
273
274    #[error("Scalar in ProveDlog reading erorr with exp: {0:?}")]
275    ScalarReadProveDlog(SigmaBoolean),
276
277    #[error("Scalar in ProveDhTumple reading erorr with exp: {0:?}")]
278    ScalarReadProveDhTuple(SigmaBoolean),
279
280    #[error("Cthreshold coeff reading erorr with exp: {0:?}")]
281    CthresholdCoeffRead(SigmaBoolean),
282
283    #[error("Error: {0:?} for top level exp: {1:?}")]
284    TopLevelExpWrap(Box<SigParsingError>, SigmaBoolean),
285}
286
287#[cfg(test)]
288#[allow(clippy::unwrap_used)]
289mod test {
290    use std::io::Cursor;
291
292    use ergotree_ir::serialization::{
293        constant_store::ConstantStore, sigma_byte_reader::SigmaByteReader,
294    };
295    use k256::Scalar;
296
297    use super::read_scalar;
298
299    // Test scalar parsing and also test handling parsing when there are less than GROUP_SIZE bytes in the buffer
300    #[test]
301    fn test_scalar_parse() {
302        let mut bytes = [0; 32];
303        bytes[31] = 1;
304
305        for i in 0..31 {
306            let cursor = Cursor::new(&bytes[i..]);
307            let mut sr = SigmaByteReader::new(cursor, ConstantStore::empty());
308            let scalar = read_scalar(&mut sr).unwrap();
309            assert_eq!(*scalar.as_scalar_ref(), Scalar::ONE);
310        }
311    }
312}
ergotree_interpreter/sigma_protocol/sig_serializer.rs

ergotree_interpreter/sigma_protocol/
sig_serializer.rs
