binius_examples/circuits/
bitcoin_block_contains_transaction.rs

1// Copyright 2025 Irreducible Inc.
2//! Proof that a Bitcoin block contains a certain transaction.
3
4use binius_circuits::bitcoin::{double_sha256::double_sha256, merkle_path::merkle_path};
5use binius_frontend::{CircuitBuilder, Wire};
6
7/// Asserts that `transaction_hash` has a valid merkle path to the merkle root in `block_header`,
8/// and that `block_header` hashes to `block_hash`.
9///
10/// **Note:** This does NOT assert that `transaction_hash` is actually the hash of a well formed
11/// transaction. In particular, `transaction_hash` might just be an internal (non-leaf) node in
12/// the transaction merkle tree, yet this circuit would pass.
13pub fn block_contains_transaction(
14	builder: &CircuitBuilder,
15	transaction_hash: [Wire; 4],
16	siblings: &[([Wire; 4], Wire)],
17	merkle_path_len: Wire,
18	block_header: [Wire; 10],
19	block_hash: [Wire; 4],
20) {
21	// extract merkle root from block header
22	let merkle_root = [
23		join(builder, block_header[5], block_header[4]),
24		join(builder, block_header[6], block_header[5]),
25		join(builder, block_header[7], block_header[6]),
26		join(builder, block_header[8], block_header[7]),
27	];
28
29	// validity of merkle path
30	builder.assert_eq_v(
31		"merkle root",
32		merkle_path(builder, transaction_hash, siblings, merkle_path_len),
33		merkle_root,
34	);
35
36	// `block_header` hashes to `block_hash`
37	builder.assert_eq_v("block hash", double_sha256(builder, &block_header), block_hash);
38}
39
40fn join(builder: &CircuitBuilder, b0: Wire, b1: Wire) -> Wire {
41	let c0 = builder.shl(b0, 32);
42	let c1 = builder.shr(b1, 32);
43	builder.bxor(c0, c1)
44}
45
46#[cfg(test)]
47mod tests {
48	use binius_circuits::bitcoin::merkle_path::SiblingSide;
49	use binius_core::Word;
50	use hex_literal::hex;
51
52	use super::*;
53
54	#[test]
55	fn test_valid() {
56		// build circuit
57		let builder = CircuitBuilder::new();
58		let transaction_hash: [Wire; 4] = std::array::from_fn(|_| builder.add_witness());
59		let siblings: Vec<([Wire; 4], Wire)> = std::iter::repeat_with(|| {
60			(std::array::from_fn(|_| builder.add_witness()), builder.add_witness())
61		})
62		.take(30)
63		.collect();
64		let merkle_path_len = builder.add_witness();
65		let block_header: [Wire; 10] = std::array::from_fn(|_| builder.add_witness());
66		let block_hash: [Wire; 4] = std::array::from_fn(|_| builder.add_witness());
67		block_contains_transaction(
68			&builder,
69			transaction_hash,
70			&siblings,
71			merkle_path_len,
72			block_header,
73			block_hash,
74		);
75		let circuit = builder.build();
76
77		// populate witness
78		let mut filler = circuit.new_witness_filler();
79		let block_header_value = hex!(
80			"000000264a14e21adad047d981c06a26446e345eda3d8beb807401000000000000000000fc01df2139954b36cebc3fa6fbf6a7160a67d34b67e5c4aa2a7ce46f5bb42a83642ea468b32c0217d14ba4d1"
81		);
82		let block_hash_value =
83			hex!("228561b085b7524957e515605725901238299ff2793300000000000000000000");
84		let transaction_hash_value =
85			hex!("6f2f044a225e8b293c6e54cf2771bf4d17ba8904b1f61cf9c392965dcbda0b83");
86		let siblings_value = vec![
87			(
88				hex!("783089645b0bc42d44e9d6a7ea62adf7a8a2adc6b7f0173d663369217b771b86"),
89				SiblingSide::Right,
90			),
91			(
92				hex!("1eeeeb0cac1753a10ade3b34bd5bf0e005cdec82545abdafa38685c45e5f8ce5"),
93				SiblingSide::Right,
94			),
95			(
96				hex!("e0d7426d603f1a817938cf366c8933d32185625fc821e3b1e964cb5f8e421501"),
97				SiblingSide::Right,
98			),
99			(
100				hex!("7af6e333025422cf892198d216f146d70efe64119071ce0ee96fd195640230df"),
101				SiblingSide::Left,
102			),
103			(
104				hex!("d848bf00d7563a26c9a43ad8cc2fa558f6a299629be20a078a6b197dcf15fc31"),
105				SiblingSide::Right,
106			),
107			(
108				hex!("b643abf3df379ac748494a5eb3025299265fff543571f8b71935e533f672c9e8"),
109				SiblingSide::Right,
110			),
111			(
112				hex!("b07d3ebc129da3ae9d1b9daee64daf74f8504ca5f9194cd006edee48b1bf4d00"),
113				SiblingSide::Right,
114			),
115			(
116				hex!("4cd4173f585e793e48aa479269f38cd986b600c494135e9de33118a8e4ac03ed"),
117				SiblingSide::Right,
118			),
119			(
120				hex!("4b5e59b8d22762cfc2906fa597b29c7eab7cd52d4b0cea9269e84e2aebce4101"),
121				SiblingSide::Right,
122			),
123			(
124				hex!("2321cd016cb8f1a29f1bad981418bed2776bf61b1a729ca86a54f14790ce822b"),
125				SiblingSide::Right,
126			),
127			(
128				hex!("fecdc8a219a271a9a969fdebf38068ffeaf25b7af353ee99e759eb0d05604218"),
129				SiblingSide::Right,
130			),
131			(
132				hex!("1736c19cc6de7296453811916ddedba46c9bbd61a3450ad3dfb8bddb698b6ad0"),
133				SiblingSide::Right,
134			),
135		];
136		filler.pack_bytes_le(&block_header, &block_header_value);
137		filler.pack_bytes_le(&block_hash, &block_hash_value);
138		filler.pack_bytes_le(&transaction_hash, &transaction_hash_value);
139		for ((sibling, is_right), (value, side)) in siblings.iter().zip(&siblings_value) {
140			filler.pack_bytes_le(sibling, value);
141			filler[*is_right] = side.to_word();
142		}
143		filler[merkle_path_len] = Word(siblings_value.len() as u64);
144		circuit.populate_wire_witness(&mut filler).unwrap();
145
146		// check
147		let constraint_system = circuit.constraint_system();
148		constraint_system.verify(&filler.into_value_vec()).unwrap();
149	}
150}
binius_examples/circuits/bitcoin_block_contains_transaction.rs

binius_examples/circuits/
bitcoin_block_contains_transaction.rs
