Skip to main content

drive_proof_verifier/block_proof/
transaction.rs

1//! A block's transactions and their execution results under the two roots of its header.
2
3use super::merkle::{merkle_root, root_from_path};
4use super::BlockProofError;
5use dapi_grpc::platform::v0::tenderdash_block_proof::Header;
6use dapi_grpc::platform::v0::TenderdashTransactionProof;
7use dapi_grpc::Message;
8use sha2::{Digest, Sha256};
9use tenderdash_abci::proto::abci::ExecTxResult;
10
11/// The hash Tenderdash knows a transaction by, which is also its leaf in the tree behind
12/// a header's `data_hash`.
13pub fn transaction_hash(transaction: &[u8]) -> [u8; 32] {
14    Sha256::digest(transaction).into()
15}
16
17/// The leaf of a transaction's execution result in the tree behind a header's
18/// `results_hash`: Tenderdash hashes only these fields of the result.
19pub fn result_leaf(code: u32, data: &[u8], gas_used: i64) -> Vec<u8> {
20    ExecTxResult {
21        code,
22        data: data.to_vec(),
23        gas_used,
24        ..Default::default()
25    }
26    .encode_to_vec()
27}
28
29/// Check that a block's contents are the ones `header` commits to: every transaction, by
30/// its hash, in block order, and the result leaf of each.
31///
32/// A block without transactions has no results, and its header commits to that too: the
33/// root of nothing.
34pub fn check_block_contents<T: AsRef<[u8]>, R: AsRef<[u8]>>(
35    header: &Header,
36    transaction_hashes: &[T],
37    result_leaves: &[R],
38) -> Result<(), BlockProofError> {
39    let height = header.height;
40    if merkle_root(transaction_hashes).as_slice() != header.data_hash {
41        return Err(BlockProofError::TransactionsRootMismatch { height });
42    }
43    if merkle_root(result_leaves).as_slice() != header.results_hash {
44        return Err(BlockProofError::ResultsRootMismatch { height });
45    }
46    Ok(())
47}
48
49/// Check that a transaction and its execution result are in the block of `header`, at the
50/// position `proof` names.
51///
52/// `proof.total` is the node's claim, which no single path settles: the paths show that
53/// the transaction and its result are in the block, and where they are only if the block
54/// holds that many transactions.
55pub fn verify_transaction_proof(
56    header: &Header,
57    transaction_hash: &[u8; 32],
58    result_leaf: &[u8],
59    proof: &TenderdashTransactionProof,
60) -> Result<(), BlockProofError> {
61    let (height, index, total) = (header.height, proof.index, proof.total);
62
63    let data_root = root_from_path(index, total, transaction_hash, &proof.transaction_path)?;
64    if data_root.as_slice() != header.data_hash {
65        return Err(BlockProofError::TransactionNotInBlock { height, index });
66    }
67    let results_root = root_from_path(index, total, result_leaf, &proof.result_path)?;
68    if results_root.as_slice() != header.results_hash {
69        return Err(BlockProofError::ResultNotInBlock { height, index });
70    }
71    Ok(())
72}
73
74#[cfg(test)]
75mod tests {
76    use super::super::merkle::MerkleTree;
77    use super::*;
78
79    fn transactions() -> Vec<Vec<u8>> {
80        (0u8..5).map(|byte| vec![byte; 3]).collect()
81    }
82
83    fn hashes() -> Vec<[u8; 32]> {
84        transactions()
85            .iter()
86            .map(|transaction| transaction_hash(transaction))
87            .collect()
88    }
89
90    fn result_leaves() -> Vec<Vec<u8>> {
91        (0u32..5)
92            .map(|index| result_leaf(index * 100, &[index as u8], i64::from(index) + 1))
93            .collect()
94    }
95
96    fn header() -> Header {
97        Header {
98            height: 7,
99            data_hash: merkle_root(&hashes()).to_vec(),
100            results_hash: merkle_root(&result_leaves()).to_vec(),
101            ..Default::default()
102        }
103    }
104
105    fn proof_of(index: usize) -> TenderdashTransactionProof {
106        TenderdashTransactionProof {
107            index: index as u32,
108            total: 5,
109            transaction_path: MerkleTree::new(&hashes(), &[index]).paths.remove(0),
110            result_path: MerkleTree::new(&result_leaves(), &[index]).paths.remove(0),
111        }
112    }
113
114    fn verify(index: usize, proof: &TenderdashTransactionProof) -> Result<(), BlockProofError> {
115        verify_transaction_proof(&header(), &hashes()[index], &result_leaves()[index], proof)
116    }
117
118    #[test]
119    fn should_encode_a_result_as_tenderdash_does() {
120        // code = 1 (varint), data = 2 (bytes), gas_used = 6 (varint)
121        assert_eq!(
122            result_leaf(40100, &[1, 2], 9),
123            [0x08, 0xa4, 0xb9, 0x02, 0x12, 0x02, 0x01, 0x02, 0x30, 0x09]
124        );
125        // zero values are not encoded
126        assert_eq!(result_leaf(0, &[], 0), Vec::<u8>::new());
127    }
128
129    #[test]
130    fn should_accept_every_transaction_of_a_block_with_its_result() {
131        for index in 0..5 {
132            assert_eq!(verify(index, &proof_of(index)), Ok(()), "{index}");
133        }
134    }
135
136    #[test]
137    fn should_refuse_another_transaction_under_a_path() {
138        let other = transaction_hash(&[9; 3]);
139
140        assert_eq!(
141            verify_transaction_proof(&header(), &other, &result_leaves()[1], &proof_of(1)),
142            Err(BlockProofError::TransactionNotInBlock {
143                height: 7,
144                index: 1
145            })
146        );
147    }
148
149    #[test]
150    fn should_refuse_another_result_under_a_path() {
151        for other in [
152            result_leaf(101, &[1], 2),
153            result_leaf(100, &[2], 2),
154            result_leaf(100, &[1], 3),
155            // the result of another transaction of the same block
156            result_leaves()[2].clone(),
157        ] {
158            assert_eq!(
159                verify_transaction_proof(&header(), &hashes()[1], &other, &proof_of(1)),
160                Err(BlockProofError::ResultNotInBlock {
161                    height: 7,
162                    index: 1
163                })
164            );
165        }
166    }
167
168    #[test]
169    fn should_refuse_a_changed_path() {
170        let mut proof = proof_of(1);
171        proof.transaction_path[0][0] ^= 1;
172        assert_eq!(
173            verify(1, &proof),
174            Err(BlockProofError::TransactionNotInBlock {
175                height: 7,
176                index: 1
177            })
178        );
179
180        let mut proof = proof_of(1);
181        proof.result_path[1][0] ^= 1;
182        assert_eq!(
183            verify(1, &proof),
184            Err(BlockProofError::ResultNotInBlock {
185                height: 7,
186                index: 1
187            })
188        );
189
190        let mut proof = proof_of(1);
191        proof.transaction_path.pop();
192        assert_eq!(
193            verify(1, &proof),
194            Err(BlockProofError::MalformedPath { index: 1, total: 5 })
195        );
196    }
197
198    #[test]
199    fn should_refuse_a_transaction_at_another_position() {
200        // position 0 has a path of the same length, hashed in another order
201        let mut proof = proof_of(1);
202        proof.index = 0;
203        assert_eq!(
204            verify(1, &proof),
205            Err(BlockProofError::TransactionNotInBlock {
206                height: 7,
207                index: 0
208            })
209        );
210
211        // position 4 of five has a shorter path
212        let mut proof = proof_of(1);
213        proof.index = 4;
214        assert_eq!(
215            verify(1, &proof),
216            Err(BlockProofError::MalformedPath { index: 4, total: 5 })
217        );
218
219        let mut proof = proof_of(1);
220        proof.index = 5;
221        assert_eq!(
222            verify(1, &proof),
223            Err(BlockProofError::IndexOutOfRange { index: 5, total: 5 })
224        );
225    }
226
227    #[test]
228    fn should_refuse_a_transaction_of_another_block() {
229        let mut header = header();
230        header.data_hash[0] ^= 1;
231        assert_eq!(
232            verify_transaction_proof(&header, &hashes()[1], &result_leaves()[1], &proof_of(1)),
233            Err(BlockProofError::TransactionNotInBlock {
234                height: 7,
235                index: 1
236            })
237        );
238    }
239
240    #[test]
241    fn should_accept_a_block_whose_contents_match_its_header() {
242        assert_eq!(
243            check_block_contents(&header(), &hashes(), &result_leaves()),
244            Ok(())
245        );
246    }
247
248    #[test]
249    fn should_refuse_contents_the_header_does_not_commit_to() {
250        let mut changed = hashes();
251        changed.swap(0, 1);
252        assert_eq!(
253            check_block_contents(&header(), &changed, &result_leaves()),
254            Err(BlockProofError::TransactionsRootMismatch { height: 7 })
255        );
256        assert_eq!(
257            check_block_contents(&header(), &hashes()[..4], &result_leaves()),
258            Err(BlockProofError::TransactionsRootMismatch { height: 7 })
259        );
260
261        let mut changed = result_leaves();
262        changed[0] = result_leaf(1, &[], 1);
263        assert_eq!(
264            check_block_contents(&header(), &hashes(), &changed),
265            Err(BlockProofError::ResultsRootMismatch { height: 7 })
266        );
267        assert_eq!(
268            check_block_contents(&header(), &hashes(), &result_leaves()[..4]),
269            Err(BlockProofError::ResultsRootMismatch { height: 7 })
270        );
271    }
272
273    #[test]
274    fn should_hold_a_block_without_transactions_to_the_root_of_no_results() {
275        let nothing: [Vec<u8>; 0] = [];
276        let mut header = Header {
277            height: 7,
278            data_hash: merkle_root(&nothing).to_vec(),
279            results_hash: merkle_root(&nothing).to_vec(),
280            ..Default::default()
281        };
282        assert_eq!(check_block_contents(&header, &nothing, &nothing), Ok(()));
283
284        header.results_hash = merkle_root(&result_leaves()).to_vec();
285        assert_eq!(
286            check_block_contents(&header, &nothing, &nothing),
287            Err(BlockProofError::ResultsRootMismatch { height: 7 })
288        );
289    }
290}