15698235808

Committed 17 Jun 2025 04:33AM UTC coverage: 78.333% (+0.04%) from 78.291%

Build # 15698235808

Build Type

Pull #804

github

Committed by

web-flow

Commit Message

Merge ed47dd2dd into 6f12ef8f2

Pull Request Pull Request #804: Add autolykos 2 validation for custom message

Run Details

49 of 62 new or added lines in 5 files covered. (79.03%)

5 existing lines in 2 files now uncovered.

11764 of 15018 relevant lines covered (78.33%)

2.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.48

/ergo-merkle-tree/src/batchmerkleproof.rs

use crate::LevelNode;
use crate::NodeSide;
use crate::{prefixed_hash2, INTERNAL_PREFIX};
use ergo_chain_types::Digest32;

#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
pub struct BatchMerkleProofIndex {
    #[cfg_attr(feature = "arbitrary", proptest(strategy = "1..u32::MAX as usize"))]
    pub index: usize,
    pub hash: Digest32,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(
    feature = "json",
    serde(into = "crate::json::BatchMerkleProofJson"),
    serde(try_from = "crate::json::BatchMerkleProofJson")
)]
#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
/// Compact Merkle multiproof. Can be created using [`crate::MerkleTree::proof_by_indices`]
/// Implementation based on <https://deepai.org/publication/compact-merkle-multiproofs>
pub struct BatchMerkleProof {
    pub(crate) indices: Vec<BatchMerkleProofIndex>,
    pub(crate) proofs: Vec<LevelNode>,
}

impl BatchMerkleProof {
    /// Create a new BatchMerkleProof
    pub fn new(indices: Vec<BatchMerkleProofIndex>, proofs: Vec<crate::LevelNode>) -> Self {
        BatchMerkleProof { indices, proofs }
    }

    /// Generates root hash of proof, and compares it against expected root hash
    pub fn valid(&self, expected_root: &[u8]) -> bool {
        fn validate(
            a: &[usize],
            e: &[BatchMerkleProofIndex],
            m: &[crate::LevelNode],
        ) -> Option<Vec<Digest32>> {
            // For each index in a, take the value of its immediate neighbor, and store each index with its neighbor
            let b: Vec<(usize, usize)> = a
                .iter()
                .map(|i| if i % 2 == 0 { (*i, i + 1) } else { (i - 1, *i) })
                .collect();

            let mut e_new = vec![];
            let mut m_new = m.to_owned();
            // E must always have the same length as B
            if e.len() != b.len() {
                return None;
            }
            let mut i = 0;
            // assign generated hashes to a new E that will be used for next iteration
            while i < b.len() {
                if b.len() > 1 && b.get(i) == b.get(i + 1) {
                    // both indices needed for computing parent hash are part of e
                    e_new.push(prefixed_hash2(
                        INTERNAL_PREFIX,
                        e[i].hash.as_ref(),
                        e[i + 1].hash.as_ref(),
                    ));
                    i += 2;
                } else {
                    // Need an additional hash from m
                    let head = if !m_new.is_empty() {
                        m_new.remove(0)
                    } else {
                        return None;
                    };

                    if head.side == NodeSide::Left {
                        e_new.push(prefixed_hash2(
                            INTERNAL_PREFIX,
                            head.hash.as_ref().map(|h| h.as_ref()),
                            e[i].hash.as_ref(),
                        ));
                    } else {
                        e_new.push(prefixed_hash2(
                            INTERNAL_PREFIX,
                            e[i].hash.as_ref(),
                            head.hash.as_ref().map(|h| h.as_ref()),
                        ));
                    }
                    i += 1;
                }
            }
            let mut a_new: Vec<usize> = b.iter().map(|(_, b)| b / 2).collect(); // Generate indices for parents of current b
            a_new.sort_unstable();
            a_new.dedup();
            // Repeat until root of tree is reached
            if (!m_new.is_empty() || e_new.len() > 1) && !a_new.is_empty() {
                let e: Vec<BatchMerkleProofIndex> = a_new
                    .iter()
                    .copied()
                    .zip(e_new)
                    .map(|(index, hash)| BatchMerkleProofIndex { index, hash })
                    .collect();
                e_new = validate(&a_new, &e, &m_new)?;
            }
            Some(e_new)
        }

        let mut e = self.indices.to_owned();
        e.sort_by_key(|BatchMerkleProofIndex { index, .. }| *index);
        let a: Vec<usize> = e
            .iter()
            .map(|BatchMerkleProofIndex { index, .. }| *index)
            .collect();
        match validate(&a, &e, &self.proofs).as_deref() {
            Some([root_hash]) => root_hash.as_ref() == expected_root,
            _ => false,
        }
    }

    /// Returns indices (leaf nodes) that are part of the proof
    pub fn get_indices(&self) -> &[BatchMerkleProofIndex] {
        &self.indices
    }
    /// Returns nodes included in proof to get to root node
    pub fn get_proofs(&self) -> &[LevelNode] {
        &self.proofs
    }
}

use sigma_ser::ScorexSerializable;

// Binary Serialization for BatchMerkleProof. Matches Scala implementation. Since the Scala implementation uses 4-byte ints for length/indices, this method will fail the proof or indexes length is > u32::MAX,
impl ScorexSerializable for BatchMerkleProof {
    fn scorex_serialize<W: sigma_ser::vlq_encode::WriteSigmaVlqExt>(
        &self,
        w: &mut W,
    ) -> sigma_ser::ScorexSerializeResult {
        w.put_u32_be_bytes(u32::try_from(self.indices.len())?)?; // for serialization, index length must be at most 4 bytes
        w.put_u32_be_bytes(u32::try_from(self.proofs.len())?)?;

        for BatchMerkleProofIndex { index, hash } in &self.indices {
            w.put_u32_be_bytes(u32::try_from(*index)?)?;
            w.write_all(hash.as_ref())?;
        }

        for proof in &self.proofs {
            match proof.hash {
                Some(ref hash) => w.write_all(hash.as_ref())?,
                None => w.write_all(&[0; 32])?,
            }
            w.put_u8(proof.side as u8)?;
        }

        Ok(())
    }

    fn scorex_parse<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(
        r: &mut R,
    ) -> Result<Self, sigma_ser::ScorexParsingError> {
        fn read_u32_be<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(
            r: &mut R,
        ) -> Result<u32, sigma_ser::ScorexParsingError> {
            let mut bytes = [0u8; 4];
            r.read_exact(&mut bytes)?;
            Ok(u32::from_be_bytes(bytes))
        }
        let indices_len = read_u32_be(r)? as usize;
        let proofs_len = read_u32_be(r)? as usize;
        let indices = (0..indices_len)
            .map(|_| {
                let index = read_u32_be(r)? as usize;
                let mut hash = Digest32::zero();
                r.read_exact(&mut hash.0[..])?;
                Ok(BatchMerkleProofIndex { index, hash })
            })
            .collect::<Result<Vec<BatchMerkleProofIndex>, sigma_ser::ScorexParsingError>>()?;

        let proofs = (0..proofs_len)
            .map(|_| {
                let mut hash = Digest32::zero();
                r.read_exact(&mut hash.0[..])?;
                let empty = hash.as_ref().iter().all(|&b| b == 0);
                let side: NodeSide = r.get_u8()?.try_into().map_err(|_| {
                    sigma_ser::ScorexParsingError::ValueOutOfBounds(
                        "Side can only be 0 or 1".into(),
                    )
                })?;

                if empty {
                    Ok(crate::LevelNode::empty_node(side))
                } else {
                    Ok(crate::LevelNode::new(hash, side))
                }
            })
            .collect::<Result<Vec<crate::LevelNode>, sigma_ser::ScorexParsingError>>()?;
        Ok(BatchMerkleProof::new(indices, proofs))
    }
}

#[cfg(test)]
#[cfg(feature = "arbitrary")]
#[allow(clippy::unwrap_used, clippy::panic)]
mod test {
    use crate::batchmerkleproof::BatchMerkleProof;
    use proptest::prelude::*;
    use sigma_ser::ScorexSerializable;
    proptest! {
        #[test]
        fn test_batchmerkleproof_serialization_roundtrip(proof in any::<BatchMerkleProof>().prop_filter("Indices > u32::max not allowed", |proof| proof.indices.len() < u32::MAX as usize)) {
            let serialized_bytes = proof.scorex_serialize_bytes().unwrap();
            assert_eq!(BatchMerkleProof::scorex_parse_bytes(&serialized_bytes).unwrap(), proof);
            assert_eq!(serialized_bytes.len(), (8 + proof.proofs.len() * 33 + proof.indices.len() * 36));
        }
        #[test]
        fn test_empty_deserialization(bytes in any::<[u8; 2]>()) {
            assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
        }
        #[test]
        fn test_invalid_deserialization(bytes in any::<[u8; 9]>()) {
            assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
        }

    }
}

1	use crate::LevelNode;
2	use crate::NodeSide;
3	use crate::{prefixed_hash2, INTERNAL_PREFIX};
4	use ergo_chain_types::Digest32;
5
6	#[derive(Debug, Clone, PartialEq, Eq)]
7	#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
8	pub struct BatchMerkleProofIndex {
9	#[cfg_attr(feature = "arbitrary", proptest(strategy = "1..u32::MAX as usize"))]
10	pub index: usize,
11	pub hash: Digest32,
12	}
13	#[derive(Debug, Clone, PartialEq, Eq)]
14	#[cfg_attr(feature = "json", derive(serde::Serialize, serde::Deserialize))]
15	#[cfg_attr(
16	feature = "json",
17	serde(into = "crate::json::BatchMerkleProofJson"),
18	serde(try_from = "crate::json::BatchMerkleProofJson")
19	)]
20	#[cfg_attr(feature = "arbitrary", derive(proptest_derive::Arbitrary))]
21	/// Compact Merkle multiproof. Can be created using [`crate::MerkleTree::proof_by_indices`]
22	/// Implementation based on <https://deepai.org/publication/compact-merkle-multiproofs>
23	pub struct BatchMerkleProof {
24	pub(crate) indices: Vec<BatchMerkleProofIndex>,
25	pub(crate) proofs: Vec<LevelNode>,
26	}
27
28	impl BatchMerkleProof {
29	/// Create a new BatchMerkleProof
30	pub fn new(indices: Vec<BatchMerkleProofIndex>, proofs: Vec<crate::LevelNode>) -> Self {	3✔
31	BatchMerkleProof { indices, proofs }
32	}
33
34	/// Generates root hash of proof, and compares it against expected root hash
35	pub fn valid(&self, expected_root: &[u8]) -> bool {	1✔
36	fn validate(	1✔
37	a: &[usize],
38	e: &[BatchMerkleProofIndex],
39	m: &[crate::LevelNode],
40	) -> Option<Vec<Digest32>> {
41	// For each index in a, take the value of its immediate neighbor, and store each index with its neighbor
42	let b: Vec<(usize, usize)> = a	1✔
43	.iter()
44	.map(\|i\| if i % 2 == 0 { (i, i + 1) } else { (i - 1, i) })	2✔
45	.collect();
46
47	let mut e_new = vec![];	1✔
48	let mut m_new = m.to_owned();	1✔
49	// E must always have the same length as B
50	if e.len() != b.len() {	2✔
51	return None;	×
52	}
53	let mut i = 0;	1✔
54	// assign generated hashes to a new E that will be used for next iteration
55	while i < b.len() {	2✔
56	if b.len() > 1 && b.get(i) == b.get(i + 1) {	5✔
57	// both indices needed for computing parent hash are part of e
58	e_new.push(prefixed_hash2(	1✔
59	INTERNAL_PREFIX,
60	e[i].hash.as_ref(),	2✔
61	e[i + 1].hash.as_ref(),	1✔
62	));
63	i += 2;	1✔
64	} else {
65	// Need an additional hash from m
66	let head = if !m_new.is_empty() {	2✔
67	m_new.remove(0)	1✔
68	} else {
69	return None;	×
70	};
71
72	if head.side == NodeSide::Left {	1✔
UNCOV 73	e_new.push(prefixed_hash2(	×
74	INTERNAL_PREFIX,
UNCOV 75	head.hash.as_ref().map(\|h\| h.as_ref()),	×
UNCOV 76	e[i].hash.as_ref(),	×
77	));
78	} else {
79	e_new.push(prefixed_hash2(	1✔
80	INTERNAL_PREFIX,
81	e[i].hash.as_ref(),	2✔
82	head.hash.as_ref().map(\|h\| h.as_ref()),	1✔
83	));
84	}
85	i += 1;	2✔
86	}
87	}
88	let mut a_new: Vec<usize> = b.iter().map(\|(_, b)\| b / 2).collect(); // Generate indices for parents of current b	4✔
89	a_new.sort_unstable();	2✔
90	a_new.dedup();	1✔
91	// Repeat until root of tree is reached
92	if (!m_new.is_empty() \|\| e_new.len() > 1) && !a_new.is_empty() {	2✔
93	let e: Vec<BatchMerkleProofIndex> = a_new	2✔
94	.iter()
95	.copied()
96	.zip(e_new)	1✔
97	.map(\|(index, hash)\| BatchMerkleProofIndex { index, hash })	2✔
98	.collect();
99	e_new = validate(&a_new, &e, &m_new)?;	2✔
100	}
101	Some(e_new)	1✔
102	}
103
104	let mut e = self.indices.to_owned();	1✔
105	e.sort_by_key(\|BatchMerkleProofIndex { index, .. }\| *index);	4✔
106	let a: Vec<usize> = e	1✔
107	.iter()
108	.map(\|BatchMerkleProofIndex { index, .. }\| *index)	2✔
109	.collect();
110	match validate(&a, &e, &self.proofs).as_deref() {	3✔
111	Some([root_hash]) => root_hash.as_ref() == expected_root,	2✔
112	_ => false,	×
113	}
114	}
115
116	/// Returns indices (leaf nodes) that are part of the proof
117	pub fn get_indices(&self) -> &[BatchMerkleProofIndex] {	1✔
118	&self.indices	1✔
119	}
120	/// Returns nodes included in proof to get to root node
121	pub fn get_proofs(&self) -> &[LevelNode] {	1✔
122	&self.proofs	1✔
123	}
124	}
125
126	use sigma_ser::ScorexSerializable;
127
128	// Binary Serialization for BatchMerkleProof. Matches Scala implementation. Since the Scala implementation uses 4-byte ints for length/indices, this method will fail the proof or indexes length is > u32::MAX,
129	impl ScorexSerializable for BatchMerkleProof {
130	fn scorex_serialize<W: sigma_ser::vlq_encode::WriteSigmaVlqExt>(	2✔
131	&self,
132	w: &mut W,
133	) -> sigma_ser::ScorexSerializeResult {
134	w.put_u32_be_bytes(u32::try_from(self.indices.len())?)?; // for serialization, index length must be at most 4 bytes	2✔
135	w.put_u32_be_bytes(u32::try_from(self.proofs.len())?)?;	2✔
136
137	for BatchMerkleProofIndex { index, hash } in &self.indices {	4✔
138	w.put_u32_be_bytes(u32::try_from(*index)?)?;	2✔
139	w.write_all(hash.as_ref())?;	2✔
140	}
141
142	for proof in &self.proofs {	4✔
143	match proof.hash {	2✔
144	Some(ref hash) => w.write_all(hash.as_ref())?,	1✔
145	None => w.write_all(&[0; 32])?,	2✔
146	}
147	w.put_u8(proof.side as u8)?;	2✔
148	}
149
150	Ok(())	2✔
151	}
152
153	fn scorex_parse<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(	3✔
154	r: &mut R,
155	) -> Result<Self, sigma_ser::ScorexParsingError> {
156	fn read_u32_be<R: sigma_ser::vlq_encode::ReadSigmaVlqExt>(	2✔
157	r: &mut R,
158	) -> Result<u32, sigma_ser::ScorexParsingError> {
159	let mut bytes = [0u8; 4];	2✔
160	r.read_exact(&mut bytes)?;	2✔
161	Ok(u32::from_be_bytes(bytes))	2✔
162	}
163	let indices_len = read_u32_be(r)? as usize;	2✔
164	let proofs_len = read_u32_be(r)? as usize;	2✔
165	let indices = (0..indices_len)	3✔
166	.map(\|_\| {	2✔
167	let index = read_u32_be(r)? as usize;	2✔
168	let mut hash = Digest32::zero();	2✔
169	r.read_exact(&mut hash.0[..])?;	2✔
170	Ok(BatchMerkleProofIndex { index, hash })	2✔
171	})
172	.collect::<Result<Vec<BatchMerkleProofIndex>, sigma_ser::ScorexParsingError>>()?;
173
174	let proofs = (0..proofs_len)	4✔
175	.map(\|_\| {	2✔
176	let mut hash = Digest32::zero();	2✔
177	r.read_exact(&mut hash.0[..])?;	2✔
178	let empty = hash.as_ref().iter().all(\|&b\| b == 0);	6✔
179	let side: NodeSide = r.get_u8()?.try_into().map_err(\|_\| {	2✔
180	sigma_ser::ScorexParsingError::ValueOutOfBounds(	×
181	"Side can only be 0 or 1".into(),	×
182	)
183	})?;
184
185	if empty {	3✔
186	Ok(crate::LevelNode::empty_node(side))	2✔
187	} else {
188	Ok(crate::LevelNode::new(hash, side))	1✔
189	}
190	})
191	.collect::<Result<Vec<crate::LevelNode>, sigma_ser::ScorexParsingError>>()?;
192	Ok(BatchMerkleProof::new(indices, proofs))	4✔
193	}
194	}
195
196	#[cfg(test)]
197	#[cfg(feature = "arbitrary")]
198	#[allow(clippy::unwrap_used, clippy::panic)]
199	mod test {
200	use crate::batchmerkleproof::BatchMerkleProof;
201	use proptest::prelude::*;
202	use sigma_ser::ScorexSerializable;
203	proptest! {
204	#[test]
205	fn test_batchmerkleproof_serialization_roundtrip(proof in any::<BatchMerkleProof>().prop_filter("Indices > u32::max not allowed", \|proof\| proof.indices.len() < u32::MAX as usize)) {
206	let serialized_bytes = proof.scorex_serialize_bytes().unwrap();
207	assert_eq!(BatchMerkleProof::scorex_parse_bytes(&serialized_bytes).unwrap(), proof);
208	assert_eq!(serialized_bytes.len(), (8 + proof.proofs.len() * 33 + proof.indices.len() * 36));
209	}
210	#[test]
211	fn test_empty_deserialization(bytes in any::<[u8; 2]>()) {
212	assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
213	}
214	#[test]
215	fn test_invalid_deserialization(bytes in any::<[u8; 9]>()) {
216	assert!(BatchMerkleProof::scorex_parse_bytes(&bytes).is_err());
217	}
218
219	}
220	}

ergoplatform / sigma-rust / 15698235808

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous