Skip to content

Add process_proof test, make it more modular #417

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Mar 22, 2025
Merged

Add process_proof test, make it more modular #417

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
180 changes: 151 additions & 29 deletions crates/floresta-chain/src/pruned_utreexo/udata.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,8 @@ use bitcoin::BlockHash;
use bitcoin::OutPoint;
use bitcoin::TxOut;
use bitcoin::VarInt;
use rustreexo::accumulator::node_hash::BitcoinNodeHash;
use rustreexo::accumulator::proof::Proof;
use sha2::Digest;
use sha2::Sha512_256;

Expand Down Expand Up @@ -198,6 +200,19 @@ pub struct BatchProof {
pub hashes: Vec<BlockHash>,
}

impl From<&BatchProof> for Proof {
fn from(batch_proof: &BatchProof) -> Self {
let targets = batch_proof.targets.iter().map(|target| target.0).collect();
let proof_hashes = batch_proof
.hashes
.iter()
.map(|hash| BitcoinNodeHash::Some(*hash.as_byte_array()))
.collect();

Proof::new(targets, proof_hashes)
}
}

/// UData contains data needed to prove the existence and validity of all inputs
/// for a Bitcoin block. With this data, a full node may only keep the utreexo
/// roots and still be able to fully validate a block.
Expand Down Expand Up @@ -306,7 +321,7 @@ pub mod proof_util {
use super::LeafData;
use crate::prelude::*;
use crate::pruned_utreexo::consensus::UTREEXO_TAG_V1;
use crate::pruned_utreexo::BlockchainInterface;
use crate::BlockchainError;
use crate::CompactLeafData;
use crate::ScriptPubkeyType;
use crate::UData;
Expand All @@ -316,6 +331,15 @@ pub mod proof_util {
EmptyStack,
}

impl From<Error> for BlockchainError {
fn from(_e: Error) -> Self {
BlockchainError::UtreexoError(
"Reconstruct Leaf Error: expected a standard pubkey type, found empty script"
.to_string(),
)
}
}

pub fn get_script_type(script: &ScriptBuf) -> ScriptPubkeyType {
if script.is_p2pkh() {
return ScriptPubkeyType::PubKeyHash;
Expand Down Expand Up @@ -431,30 +455,29 @@ pub mod proof_util {
}

#[allow(clippy::type_complexity)]
pub fn process_proof<Chain: BlockchainInterface>(
pub fn process_proof<F, E>(
udata: &UData,
transactions: &[Transaction],
chain: &Chain,
) -> Result<(Proof, Vec<sha256::Hash>, HashMap<OutPoint, TxOut>), Chain::Error> {
let targets = udata.proof.targets.iter().map(|target| target.0).collect();
let hashes = udata
.proof
.hashes
.iter()
.map(|hash| BitcoinNodeHash::Some(*hash.as_byte_array()))
.collect();
let proof = Proof::new(targets, hashes);
let mut hashes = Vec::new();
let mut leaves_iter = udata.leaves.iter().cloned();
let mut tx_iter = transactions.iter();
get_block_hash: F,
) -> Result<(Proof, Vec<sha256::Hash>, HashMap<OutPoint, TxOut>), E>
where
F: Fn(u32) -> Result<BlockHash, E>,
E: From<Error>,
{
// Initialize return values
let proof = Proof::from(&udata.proof);
let mut del_hashes = Vec::new();
let mut utxos = HashMap::new();

let mut inputs = HashMap::new();
tx_iter.next(); // Skip coinbase
let mut leaves_iter = udata.leaves.iter().cloned();

for tx in tx_iter {
// Skip coinbase transaction
for tx in transactions.iter().skip(1) {
let txid = tx.compute_txid();

// Collect new UTXOs, which may be spent by later transactions in the block
for (vout, out) in tx.output.iter().enumerate() {
inputs.insert(
utxos.insert(
OutPoint {
txid,
vout: vout as u32,
Expand All @@ -464,20 +487,26 @@ pub mod proof_util {
}

for input in tx.input.iter() {
if !inputs.contains_key(&input.previous_output) {
if let Some(leaf) = leaves_iter.next() {
let height = leaf.header_code >> 1;
let hash = chain.get_block_hash(height)?;
let leaf =
reconstruct_leaf_data(&leaf, input, hash).expect("Invalid proof");
hashes.push(leaf._get_leaf_hashes());
inputs.insert(leaf.prevout, leaf.utxo);
}
// Only reconstruct UTXOs missing from the map, from prior blocks. Transactions
// spending uncreated UTXOs yield an invalid deletion hash, failing utreexo verification.
if utxos.contains_key(&input.previous_output) {
continue;
}
let leaf = match leaves_iter.next() {
Some(leaf) => leaf,
None => continue,
};

let height = leaf.header_code >> 1;
let hash = get_block_hash(height)?;
let leaf = reconstruct_leaf_data(&leaf, input, hash)?;
// Push the UTXO to remove from the set and its leaf hash (deletion hash)
del_hashes.push(leaf._get_leaf_hashes());
utxos.insert(leaf.prevout, leaf.utxo);
}
}

Ok((proof, hashes, inputs))
Ok((proof, del_hashes, utxos))
}

pub fn reconstruct_script_pubkey(
Expand Down Expand Up @@ -537,22 +566,115 @@ pub mod proof_util {
Err(Error::EmptyStack)
}
}

#[cfg(test)]
mod test {
extern crate std;

use std::format;
use std::str::FromStr;

use bitcoin::consensus::encode::deserialize_hex;
use bitcoin::hashes::sha256;
use bitcoin::Amount;
use bitcoin::BlockHash;
use bitcoin::ScriptBuf;
use bitcoin::Transaction;
use floresta_common::acchashes;
use floresta_common::bhash;
use rustreexo::accumulator::node_hash::BitcoinNodeHash;
use rustreexo::accumulator::stump::Stump;

use super::proof_util::reconstruct_leaf_data;
use super::CompactLeafData;
use super::LeafData;
use super::ScriptPubkeyType;
use crate::proof_util::process_proof;
use crate::AssumeValidArg;
use crate::BlockchainError;
use crate::ChainState;
use crate::KvChainStore;
use crate::Network;
use crate::UtreexoBlock;

fn setup_test_chain<'a>(
network: Network,
assume_valid_arg: AssumeValidArg,
) -> ChainState<KvChainStore<'a>> {
let test_id = rand::random::<u64>();
let chainstore = KvChainStore::new(format!("./tmp-db/{test_id}/")).unwrap();
ChainState::new(chainstore, network, assume_valid_arg)
}

fn to_acc_hashes(vec: Vec<sha256::Hash>) -> Vec<BitcoinNodeHash> {
vec.into_iter().map(Into::into).collect()
}

#[test]
fn test_process_proof_utxo_order() {
// STEP 0: Set up the block and utreexo data
let utreexo_block: UtreexoBlock = deserialize_hex("0100000011d60326c600e89bcea01a9884670bff6ba841728e70cd959d04000000000000a358f735ae382a260b709e818d55d5074f4bf0a930293a58e27baf19f18e9d203d19254f3fd40c1a62aa10e50b01000000010000000000000000000000000000000000000000000000000000000000000000ffffffff34043e19254f010a2c4d4d3d3d8eb7a0c4ff07bdb0eb81f5f85f5c6865a9abc1552cfd4119191682bb5d9007910100000000000000ffffffff01a078072a0100000023210278aac0dccc3046120e0076a4cbfef47d4ff1d407f9597ffc21062ab55be3b2f7ac0000000001000000015f2cf7f37d5a83fc9ad514e42d415ef0342574712ecc365f55ca7c0ba79e12ba000000008b483045022100ef215fbea3427afaefccfe6159e63d303e2d658b46adf3de0e5e2c11f5590f2e022074bc3f5ae713290db79dfcef41ab669d92558a2b2f7f64c81e83f14ca887b841014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff02aee8371e010000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac00c2eb0b000000001976a91400591cd5fe5cfcefb38fa3d5ca7b1667ec52ac3388ac000000000100000001d71be7b3b3ea37c8ee8bbdc588366a6555e4cbeeca5173cd0d634a109716f630000000008a47304402200cba67f2c1e806ae2e5ee5a893cc55f549cf0af530cd86e532873b94552b5144022059249e1f3ca460f4d0661f3b3f00c59699e1fd4b50ec5396caaa4133aa27004e014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff0267cafb1d010000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac00127a00000000001976a914987c9643069837ea82cdfc6287fc74e7766fde2f88ac0000000001000000019574d909d8de1697acf4674d7031d28adb28b834c1b295ba80911a593f9003ad000000008b483045022023e6d08ec35dd9b7f77fb5eb6806647fb7bf2c46b056ccfa57314ccbe64eff0602210093d134951d33d139ebd20df4e6ce1a9b756cf49913f858415e965644b9e4afd6014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff020adc3415010000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac0024f400000000001976a914c5d64c5c00d62d80a69ae7d63dc081edc71dbc8e88ac0000000001000000011b1389c7ec6011d1a7f80d097607273bc0eb4fca4090936cfd13c4187469e6d3000000008b48304502204f4119c864e8a0e646b83740979db2f330e2b64243f2da7d85b931762ee0a673022100d7f909522d6c55dc899773d5c810dfea3837012b008876fd9a4094441f8a7b54014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff02f26065ff000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac00e1f505000000001976a914f54b60efd3e70eb2f4866e7bd8db698bb13aa59788ac000000000100000001d3f9fc5aad3884b447e5921fe747e5aa6c1ef5bc354dfa96c5154e9d8aad40fb000000008a473044022002f329d215d6ea3311003ae5a996122f25e404864df4792f7094b34e823fdc37022000d573a1d114ebf43428e79280c853ceb46aa390fb075459d59454a755d3174d014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff02d00cebeb000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac40420f00000000001976a91412257a70afb08e512cb9f91479a1edb9de6b81fe88ac000000000100000001507ee46589e2a81df64e2d5ee008c27e6a4e928fa95b7648da9328c1e9f91a9c000000008b483045022100e50513d07dca027abe419e9ef4eed989e40b4ea0a70e06db0aa3545752379419022011aa017ed5de218379ac6dd087563c086b7d4468a39dbb2b3128283e7117751d014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff02c5b57fe6000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac00879303000000001976a914212441eebd4f77e2e3ef8c2d1bf0ff1687b3c87a88ac000000000100000001052a4d7756177801ace95de9b4d90d1f4bc7dfdb757baad72696453aa26085f8000000008a47304402207d692726dde4ef6bc88dd91e42d2d0df3098bff898fe739ab0599225d63c5a91022029224f844ca00e43f091c951a913012b7fbbad51619d5724149a7cf0dbe62b97014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff0240dc64b0000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688acc000f837000000001976a914968845256e95c1982a9e60f060ea39f35792f0b788ac000000000100000001fb4cbcbd2436c632f73db5272608acb8dee23733d05f10b3f376f0c0d7b75cbd000000008b48304502210092b1b11f12176a708291b608c259eaff9ce3e98fb9db66175da25374860668f7022048f55939440743f9925b3d34232e613715718d10119a5c23c71f46cdacb49f63014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff0293816e27000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac88685a00000000001976a9140d238c7c0ce909d511c193efcccb804584f6dbf888ac0000000001000000013afec4b3b670276e281bf3b6626ced8bc8356faee44348cbb4c65096af7dabfd000000008b483045022100e1cfbe6cdb54d081614fe2675d8554fdbd9271d616d875df30b046dd55d991be022013b9b63e78b260300a32219a2631f6b86d68492415c0f1b228010b195c6d3e53014104e1412429a76076dc25b2a7fc98c93da7b6e3e8045d48fecc3cb67c9163f6d616392458bdbf1e25c50171883619f91992dfe0abbecaac307e23be8e26ce9d19f8ffffffff0380a20442000000001976a914cea0534850d52cc6f19dadaf93ce30db9302187c88ac20a10700000000001976a9142911fad6636d73faea7ada74a30032c32620a94f88ac20a10700000000001976a914618118641b48c1679a3cc7ad00a9d246aa695fd888ac0000000001000000018fb56eb2ccdd91d7eb42e3e47515c828470ab88e721463fcafe9e7122e143f65000000008a47304402203fcdb0b731282e5a142305a304d23737a84ae8c7ce4bdd54d477846b572939d502205fbf74660a1a6f3eaaa48e0c5d24d9178f94c12498a269056d970f190a00197f0141040fed4775d5f5b47f2d73b35974b26ae19ccbde2c5a2ce741e5172c0baaa32bd30c23c664a5b91d84cf6c59e62a1c217dc318e24ce42977cbd8eaa89046d57639ffffffff0f005a6202000000001976a914dfcc1e75593def6563d3e35fa6615be5fd4f560e88ac80f0fa02000000001976a914ba23c86fe7c519d30f743e3491a67ef5d27c447388ac00e1f505000000001976a914dab269b027f6432ae7a6c34930485a4c8c9f5ace88ac0065cd1d000000001976a91408645206ee8a59c8d876e8bbb1a9512f5b1b14ea88ac00e1f505000000001976a914f16e0dbc76ccf3018f381b7726ce83cf874e444e88ac00e1f505000000001976a9146d293ad798d4cba8532b4f604e5c585674593d3b88ac00e1f505000000001976a91427be1119f8de54a8a7d3e65f131c6ca42eed7ba888ac80969800000000001976a914075c1dd720c63e10588b7a158aa7f43d4a6dd56288ac80969800000000001976a914c7d4c137526e35257fb94af3bd862fd8f1b65b5f88ac00e1f505000000001976a91495913e7275bfb35b3a0a9b749a013d56e54791f788ac80969800000000001976a914539845befa9b3017e0e42bfc6d1806b1d04dea2488ac00e1f505000000001976a9140a25839f64951ab152d0983d88d32cdc59120f7b88ace0151718000000001976a914ae4568bb485b0859c0d6db04d2094f3e5c43d2ce88ac80969800000000001976a9148c5a2a5c19f3f492a7df212c41f5e6df3504f4e988ac00879303000000001976a91425570998b4dfd2eb7c892c6d61772b0d209b050588ac00000000000afe2d024900fe46024900fe4a024900fe48024900fe4c024900fe4e024900fe50024900febd014900fee8024900fee602490021db2d9d4e21d41ec389811a282bddd70d2822bbc31d5c36bd25f2f7268bd2660ef15151f2df93ade1fa38c3807f6cb7446c5eb78131f188a5b5f4049b6b337090bf472b504976cbe726b549ca6fdd5aa198e0340eef4cc54609dd2b1b0e287d85379f13885795902a87a71e2c118dcf92e7b8d63d6ee2db727d1d535082817b5bf7b687299b0f8bedba623915bc8c11f37bbb852ee132ed28f1662dacd237babe4c0a5a306f1e0415e2db8e14d260c02f4b55f79552aff452bef1d66024c1ec07c365744675c11701c8b79cb942b42f5b120597dbe0ab2da7d60d502d799de9a91d11fb7546e30eb3e402bcca609436f3bb324808e0c143064799bd33691d892f60722b6bbacc53f9ceedf13dc0d88d93f7b407745537b0121fbb02e77b875995375b3b3cffc1c8b7101b45bfe963f91a5916bc46f755cfe578b21c2fa65d8caccbb69854d0246e0166f677ca4faeb7320523dc78b1d3c52d5a27700ba1f6061a6ca5297daa71ee816589e733bd455da6677aed14f0dde90c083dac1da7284e3fb72d97eb35051d774aa71fe3d434e28c227dbd53c1ae166ae76ac6fbaa744641d4a1050efbbc3c752f0a22f4187f600b8fe6be363597512ed6b5425ce017057b155edc7b9d3d04c52ab698cec15e32eeeb87e9b7bbc49ef6e1f25fd2400d2dda47c7239006477bcb15d5c5adb17e36b8df6ee0e26c8c778cdd21e8b3bd4970e3cc89d33d3ee3e6f16c00249e2a562f0f99a33fa12ae0130a67c137619d58c04a0e50e464bced58301ab8c0992b26653a15c0b2866e4af60d1172013d2d84c017c07cf7352220e579bb7989d938f34ac88cd73b45bf5e653346fd163380a5db1aa5537f1d2fafa09311dbf3c1478e16e21caed7eaebfab03c55cd7968f099d64a36411a4d7e2d23d7fa99ad8a33d701480ecfd426772d1961a0038af07bc3fca40d5ee4c9a212f5e1c437466d1f00875a6d42d04edfdafefd71046b96e1df309571bda1cbe97e8dc8b5efa0581a48e5d8fbe26066c01571b7dd6de32bc06d827bd78a03a80cff2b53374cc6fa61efff77aeda1e602a256b72f328187abb359bf10b60a36d599e18bbd71c98ee5dd910ba5efdad88ee45de41bd7fdb1775fcadcd60f9bc4e144f040e667cea94049d7f1df31cb54594da5879d027783bde41d4b658a2c540e41a2c04ff5b4169a2ee5492fe6a17e27700fb85bb717f4c5c955acb12f52bce5b9b7c90656cf9bbda51b0e80c82c9b4ff7967b1c0c8c5908d6c1c71e23b75268a6ada55750ff0a6e0d2c6ec3e29051aa5e632ad1bdc2c457fde45de454ca8e544b3c57da06acad7e3fff8aa0e23227fb9e40f192591f7d015d770e620187e065b47e8c5909d26a63a2da2047b26755c3970719c06285f7baa81e4071019ec78ca45522155090f11d42bff420034095608bc466cebcd51ba00514bcee815e587430248a07f9da39b0f3b2f2fafa5f667c59a9a03d1a7e2c7463433130a04040500aeaa232a01000000010404050067dc751e0100000001040405000a002916010000000104040500f2415b05010000000104040500104ffaeb000000000104040500c53c13ea00000000010404050000dd5ce80000000001fc0305001beac82700000000010804050010a81442000000000108040500b0affb640000000001").unwrap();
let height = 164_357;
let udata = utreexo_block.udata.as_ref().unwrap();
let txdata = &utreexo_block.block.txdata;

// This block spends UTXOs from three previous blocks
let get_block_hash = |height| match height {
164_354 => Ok(bhash!(
"0000000000000274e38b79d9c971de45f66d80bd2a586efa3e947ab448c65f0a"
)),
164_350 => Ok(bhash!(
"0000000000000305e4bb508c0b92a288ccac79b4c06bb92220a12650589e79df"
)),
164_356 => Ok(bhash!(
"000000000000049d95cd708e7241a86bff0b6784981aa0ce9be800c62603d611"
)),
_ => Err(BlockchainError::BlockNotPresent),
};

let state = setup_test_chain(Network::Bitcoin, AssumeValidArg::Disabled);
let acc = Stump {
leaves: 4784881,
roots: acchashes![
"ad9b9fc757b185e729219b88c01011ddc57f7c009c16d52b45f18e03e4e4c8b8",
"dc2a0fd968da4098822fb9941e7cd448336a6f8c4f0c3d5f170f6ea7323e125d",
"6b6020ee6bb92cdd976b099de8e5ad86dd82a002b046899414006409149ddcd3",
"158861d1078a9f394313afacaf70dd653d6439fcab287964cb1ff15ee0a4e232",
"89000eaf560a5ba3a15af0dd3cf06aab929a9478060e0d4eda6e215f81ea82c7",
"fae7b8f7dc1c8d2476002baa278b0381eebf88359c2da052228e3ea9110a67b4",
"346b5f1bede34d73d9cdf3a78d29a35785a903abc397a1ce614a41158bc0bf7d",
"b6b56f1ccc990e380ce8c528bb20d92919653d2c12d6d794aa7bac84ca9458e0",
"7cad5f60ff32a8939d803d289c4d15cc44e98a2db2aa47e79bcf6712ea745ba6",
]
.to_vec(),
};

// STEP 1: Verify the accumulator and the block
let (proof, del_hashes, inputs) = process_proof(udata, txdata, get_block_hash).unwrap();

if !acc.verify(&proof, &to_acc_hashes(del_hashes)).unwrap() {
panic!("Proof must be valid")
}
state
.validate_block_no_acc(&utreexo_block.block, height, inputs)
.expect("Block validation must pass for the given UTXOs map");

// STEP 2: Add a tx that tries to spend an UTXO created later in the block; utreexo fails
let spending_tx: Transaction = deserialize_hex("0100000001ed5598cd2a9d8c4782e553dfc149a4a14402d1e4cfe61ae104f8cdf116486341000000008b483045022100aa2d2e5647b2ee15e42effd358946ce7d9515e5a56c21c9f6661b8d3f6f3fc51022028e433bcd457cb40bfdc253d6448f3bc2fc5bb7cc417cbf2458a9803489b9be5014104a39b9e4fbd213ef24bb9be69de4a118dd0644082e47c01fd9159d38637b83fbcdc115a5d6e970586a012d1cfe3e3a8b1a3d04e763bdc5a071c0e827c0bd834a5ffffffff0213ebd526000000001976a9140568015a9facccfd09d70d409b6fc1a5546cecc688ac80969800000000001976a91449bab0d204e6c1fdf99b0b8e0ebf70ab6421e2f488ac00000000").unwrap();
assert_eq!(
format!("{}", spending_tx.compute_txid()),
"d55a5cb093e7d354ebb4ae3ecc12f281f17ca1194ff1d3ab16dd97cfd7eacf46",
);

let mut invalid_txdata = txdata.clone();
invalid_txdata.insert(1, spending_tx);

let (proof, del_hashes, _) = process_proof(udata, &invalid_txdata, get_block_hash).unwrap();

if acc.verify(&proof, &to_acc_hashes(del_hashes)).unwrap() {
panic!("Proof must be invalid")
}
}

macro_rules! test_recover_spk {
(
Expand Down
Loading