Merge PR 'Only fetch TXIDs instead of entire block during gossip verification' (#4846)

### lightning-block-sync/src/convert.rs
@@ -4,11 +4,12 @@ use crate::rpc::RpcClientError;
 use crate::utils::hex_to_work;
 use crate::{BlockHeaderData, BlockSourceError};
 
+use bitcoin::amount::Amount;
 use bitcoin::block::{Block, Header};
 use bitcoin::consensus::encode;
 use bitcoin::hash_types::{BlockHash, TxMerkleNode, Txid};
 use bitcoin::hex::FromHex;
-use bitcoin::Transaction;
+use bitcoin::{ScriptBuf, Transaction, TxOut};
 
 use serde_json;
 
@@ -295,23 +296,89 @@ impl TryInto<BlockHash> for JsonResponse {
 	}
 }
 
-/// The REST `getutxos` endpoint retuns a whole pile of data we don't care about and one bit we do
-/// - whether the `hit bitmap` field had any entries. Thus we condense the result down into only
-/// that.
+/// Converts a JSON value into the txids of a block's transactions. The JSON value is expected to
+/// be an object with a `tx` array of txid strings, as returned by the `getblock` RPC with
+/// verbosity 1 or the REST `block/notxdetails` endpoint.
+impl TryInto<Vec<Txid>> for JsonResponse {
+	type Error = &'static str;
+
+	fn try_into(self) -> Result<Vec<Txid>, &'static str> {
+		let txid_list = self
+			.0
+			.as_object()
+			.ok_or("expected JSON object")?
+			.get("tx")
+			.ok_or("missing tx field")?
+			.as_array()
+			.ok_or("expected JSON array")?;
+		let mut txids = Vec::with_capacity(txid_list.len());
+		for txid in txid_list {
+			let txid_str = txid.as_str().ok_or("expected JSON string")?;
+			txids.push(Txid::from_str(txid_str).map_err(|_| "invalid txid")?);
+		}
+		Ok(txids)
+	}
+}
+
+/// Converts a JSON value into a transaction output. The JSON value is expected to be an object
+/// with a `value` field and a `scriptPubKey` object containing a `hex` field, as returned by the
+/// `gettxout` RPC and in the entries of a REST `getutxos` response.
+impl TryInto<TxOut> for JsonResponse {
+	type Error = &'static str;
+
+	fn try_into(self) -> Result<TxOut, &'static str> {
+		let value_btc = self
+			.0
+			.get("value")
+			.ok_or("missing value field")?
+			.as_f64()
+			.ok_or("expected JSON number")?;
+		let value = Amount::from_btc(value_btc).map_err(|_| "invalid value")?;
+		let script_hex = self
+			.0
+			.get("scriptPubKey")
+			.ok_or("missing scriptPubKey field")?
+			.get("hex")
+			.ok_or("missing script hex field")?
+			.as_str()
+			.ok_or("expected JSON string")?;
+		let script_pubkey = ScriptBuf::from_hex(script_hex).map_err(|_| "invalid script hex")?;
+		Ok(TxOut { value, script_pubkey })
+	}
+}
+
+/// Converts a JSON value into an unspent transaction output as returned by the `gettxout` RPC. A
+/// `null` response indicates the output doesn't exist or has been spent.
+impl TryInto<Option<TxOut>> for JsonResponse {
+	type Error = &'static str;
+
+	fn try_into(self) -> Result<Option<TxOut>, &'static str> {
+		if self.0.is_null() {
+			return Ok(None);
+		}
+		let txout: TxOut = self.try_into()?;
+		Ok(Some(txout))
+	}
+}
+
+/// The REST `getutxos` endpoint returns a whole pile of data we don't care about beyond whether
+/// the queried output is a member of the UTXO set (i.e. the `hit bitmap` field had an entry) and,
+/// if so, the output itself. Thus we condense the result down into only that.
 #[cfg(feature = "rest-client")]
 pub(crate) struct GetUtxosResponse {
-	pub(crate) hit_bitmap_nonempty: bool,
+	pub(crate) utxo: Option<TxOut>,
 }
 
 #[cfg(feature = "rest-client")]
 impl TryInto<GetUtxosResponse> for JsonResponse {
 	type Error = &'static str;
 
 	fn try_into(self) -> Result<GetUtxosResponse, &'static str> {
-		let bitmap_str = self
-			.0
-			.as_object()
-			.ok_or("expected an object")?
+		if !self.0.is_object() {
+			return Err("expected an object");
+		}
+		let mut response = self.0;
+		let bitmap_str = response
 			.get("bitmap")
 			.ok_or("missing bitmap field")?
 			.as_str()
@@ -325,7 +392,16 @@ impl TryInto<GetUtxosResponse> for JsonResponse {
 				hit_bitmap_nonempty = true;
 			}
 		}
-		Ok(GetUtxosResponse { hit_bitmap_nonempty })
+		if !hit_bitmap_nonempty {
+			return Ok(GetUtxosResponse { utxo: None });
+		}
+		let utxo = response
+			.get_mut("utxos")
+			.ok_or("missing utxos field")?
+			.get_mut(0)
+			.ok_or("missing utxo entry")?
+			.take();
+		Ok(GetUtxosResponse { utxo: Some(JsonResponse(utxo).try_into()?) })
 	}
 }
 
@@ -774,4 +850,52 @@ pub(crate) mod tests {
 			Ok(_) => panic!("Expected error"),
 		}
 	}
+
+	#[test]
+	fn into_txid_vec_from_json_response_with_invalid_txid_data() {
+		let response = JsonResponse(serde_json::json!({ "tx": ["foobar"] }));
+		match TryInto::<Vec<Txid>>::try_into(response) {
+			Err(e) => {
+				assert_eq!(e, "invalid txid");
+			},
+			Ok(_) => panic!("Expected error"),
+		}
+	}
+
+	#[test]
+	fn into_txid_vec_from_json_response_with_valid_txid_data() {
+		let txids = vec![Txid::from_slice(&[1; 32]).unwrap(), Txid::from_slice(&[2; 32]).unwrap()];
+		let response = JsonResponse(serde_json::json!({
+			"tx": txids.iter().map(|txid| txid.to_string()).collect::<Vec<_>>(),
+		}));
+		match TryInto::<Vec<Txid>>::try_into(response) {
+			Err(e) => panic!("Unexpected error: {:?}", e),
+			Ok(parsed) => assert_eq!(parsed, txids),
+		}
+	}
+
+	#[test]
+	fn into_txout_from_json_response_with_null() {
+		let response = JsonResponse(serde_json::Value::Null);
+		match TryInto::<Option<TxOut>>::try_into(response) {
+			Err(e) => panic!("Unexpected error: {:?}", e),
+			Ok(txout) => assert_eq!(txout, None),
+		}
+	}
+
+	#[test]
+	fn into_txout_from_json_response_with_valid_txout() {
+		let response = JsonResponse(serde_json::json!({
+			"value": 0.07,
+			"scriptPubKey": { "hex": "0014abcd" },
+		}));
+		match TryInto::<Option<TxOut>>::try_into(response) {
+			Err(e) => panic!("Unexpected error: {:?}", e),
+			Ok(txout) => {
+				let txout = txout.unwrap();
+				assert_eq!(txout.value.to_sat(), 7_000_000);
+				assert_eq!(txout.script_pubkey.to_bytes(), vec![0x00, 0x14, 0xab, 0xcd]);
+			},
+		}
+	}
 }

### lightning-block-sync/src/gossip.rs
@@ -2,11 +2,10 @@
 //! current UTXO set. This module defines an implementation of the LDK API required to do so
 //! against a [`BlockSource`] which implements a few additional methods for accessing the UTXO set.
 
-use crate::{BlockData, BlockSource, BlockSourceError, BlockSourceResult};
+use crate::{BlockSource, BlockSourceError, BlockSourceResult};
 
-use bitcoin::block::Block;
 use bitcoin::constants::ChainHash;
-use bitcoin::hash_types::BlockHash;
+use bitcoin::hash_types::{BlockHash, Txid};
 use bitcoin::transaction::{OutPoint, TxOut};
 
 use lightning::routing::utxo::{UtxoFuture, UtxoLookup, UtxoLookupError, UtxoResult};
@@ -20,26 +19,28 @@ use std::pin::{pin, Pin};
 use std::sync::{Arc, Mutex};
 use std::task::Poll;
 
-/// A trait which extends [`BlockSource`] and can be queried to fetch the block at a given height
-/// as well as whether a given output is unspent (i.e. a member of the current UTXO set).
-///
-/// Note that while this is implementable for a [`BlockSource`] which returns filtered block data
-/// (i.e. [`BlockData::HeaderOnly`] for [`BlockSource::get_block`] requests), such an
-/// implementation will reject all gossip as it is not fully able to verify the UTXOs referenced.
+/// A trait which extends [`BlockSource`] and can be queried to fetch the txids of the
+/// transactions in a block as well as outputs which are members of the current UTXO set.
 pub trait UtxoSource: BlockSource + 'static {
 	/// Fetches the block hash of the block at the given height.
 	///
-	/// This will, in turn, be passed to to [`BlockSource::get_block`] to fetch the block needed
-	/// for gossip validation.
+	/// This will, in turn, be passed to [`Self::get_block_txids`] to fetch the txids of the block
+	/// needed for gossip validation.
 	fn get_block_hash_by_height<'a>(
 		&'a self, block_height: u32,
 	) -> impl Future<Output = BlockSourceResult<BlockHash>> + Send + 'a;
 
-	/// Returns true if the given output has *not* been spent, i.e. is a member of the current UTXO
-	/// set.
-	fn is_output_unspent<'a>(
+	/// Fetches the txids of all transactions in the block with the given hash, in the order the
+	/// transactions appear in the block.
+	fn get_block_txids<'a>(
+		&'a self, block_hash: &'a BlockHash,
+	) -> impl Future<Output = BlockSourceResult<Vec<Txid>>> + Send + 'a;
+
+	/// Returns the output at the given outpoint if it has *not* been spent, i.e. is a member of
+	/// the current UTXO set, or `None` otherwise.
+	fn get_unspent_txout<'a>(
 		&'a self, outpoint: OutPoint,
-	) -> impl Future<Output = BlockSourceResult<bool>> + Send + 'a;
+	) -> impl Future<Output = BlockSourceResult<Option<TxOut>>> + Send + 'a;
 }
 
 #[cfg(feature = "tokio")]
@@ -135,10 +136,10 @@ where
 {
 	source: Blocks,
 	spawn: S,
-	block_cache: Arc<Mutex<VecDeque<(u32, Block)>>>,
+	txid_cache: Arc<Mutex<VecDeque<(u32, Vec<Txid>)>>>,
 }
 
-const BLOCK_CACHE_SIZE: usize = 5;
+const TXID_CACHE_SIZE: usize = 50;
 
 impl<S: FutureSpawner, Blocks: Deref + Send + Sync + Clone> GossipVerifier<S, Blocks>
 where
@@ -151,44 +152,34 @@ where
 		Self {
 			source,
 			spawn,
-			block_cache: Arc::new(Mutex::new(VecDeque::with_capacity(BLOCK_CACHE_SIZE))),
+			txid_cache: Arc::new(Mutex::new(VecDeque::with_capacity(TXID_CACHE_SIZE))),
 		}
 	}
 
 	async fn retrieve_utxo(
-		source: Blocks, block_cache: Arc<Mutex<VecDeque<(u32, Block)>>>, short_channel_id: u64,
+		source: Blocks, txid_cache: Arc<Mutex<VecDeque<(u32, Vec<Txid>)>>>, short_channel_id: u64,
 	) -> Result<TxOut, UtxoLookupError> {
 		let block_height = (short_channel_id >> 5 * 8) as u32; // block height is most significant three bytes
 		let transaction_index = ((short_channel_id >> 2 * 8) & 0xffffff) as u32;
 		let output_index = (short_channel_id & 0xffff) as u16;
 
-		let (outpoint, output);
-
-		'tx_found: loop {
-			macro_rules! process_block {
-				($block: expr) => {{
-					if transaction_index as usize >= $block.txdata.len() {
-						return Err(UtxoLookupError::UnknownTx);
-					}
-					let transaction = &$block.txdata[transaction_index as usize];
-					if output_index as usize >= transaction.output.len() {
+		let mut cached_txid = None;
+		{
+			let recent_blocks = txid_cache.lock().unwrap();
+			for (height, txids) in recent_blocks.iter() {
+				if *height == block_height {
+					if transaction_index as usize >= txids.len() {
 						return Err(UtxoLookupError::UnknownTx);
 					}
-
-					outpoint = OutPoint::new(transaction.compute_txid(), output_index.into());
-					output = transaction.output[output_index as usize].clone();
-				}};
-			}
-			{
-				let recent_blocks = block_cache.lock().unwrap();
-				for (height, block) in recent_blocks.iter() {
-					if *height == block_height {
-						process_block!(block);
-						break 'tx_found;
-					}
+					cached_txid = Some(txids[transaction_index as usize]);
+					break;
 				}
 			}
+		}
 
+		let txid = if let Some(txid) = cached_txid {
+			txid
+		} else {
 			let ((_, tip_height_opt), block_hash) = Joiner::new(
 				pin!(source.get_best_block()),
 				pin!(source.get_block_hash_by_height(block_height)),
@@ -205,37 +196,30 @@ where
 					return Err(UtxoLookupError::UnknownTx);
 				}
 			}
-			let block_data =
-				source.get_block(&block_hash).await.map_err(|_| UtxoLookupError::UnknownTx)?;
-			let block = match block_data {
-				BlockData::HeaderOnly(_) => return Err(UtxoLookupError::UnknownTx),
-				BlockData::FullBlock(block) => block,
-			};
-			process_block!(block);
+			let txids = source
+				.get_block_txids(&block_hash)
+				.await
+				.map_err(|_| UtxoLookupError::UnknownTx)?;
+			if transaction_index as usize >= txids.len() {
+				return Err(UtxoLookupError::UnknownTx);
+			}
+			let txid = txids[transaction_index as usize];
 			{
-				let mut recent_blocks = block_cache.lock().unwrap();
-				let mut insert = true;
-				for (height, _) in recent_blocks.iter() {
-					if *height == block_height {
-						insert = false;
-					}
-				}
-				if insert {
-					if recent_blocks.len() >= BLOCK_CACHE_SIZE {
+				let mut recent_blocks = txid_cache.lock().unwrap();
+				if !recent_blocks.iter().any(|(height, _)| *height == block_height) {
+					if recent_blocks.len() >= TXID_CACHE_SIZE {
 						recent_blocks.pop_front();
 					}
-					recent_blocks.push_back((block_height, block));
+					recent_blocks.push_back((block_height, txids));
 				}
 			}
-			break 'tx_found;
-		}
-		let outpoint_unspent =
-			source.is_output_unspent(outpoint).await.map_err(|_| UtxoLookupError::UnknownTx)?;
-		if outpoint_unspent {
-			Ok(output)
-		} else {
-			Err(UtxoLookupError::UnknownTx)
-		}
+			txid
+		};
+
+		let outpoint = OutPoint::new(txid, output_index.into());
+		let txout =
+			source.get_unspent_txout(outpoint).await.map_err(|_| UtxoLookupError::UnknownTx)?;
+		txout.ok_or(UtxoLookupError::UnknownTx)
 	}
 }
 
@@ -247,9 +231,9 @@ where
 		let res = UtxoFuture::new(notifier);
 		let fut = res.clone();
 		let source = self.source.clone();
-		let block_cache = Arc::clone(&self.block_cache);
+		let txid_cache = Arc::clone(&self.txid_cache);
 		let _not_polled = self.spawn.spawn(async move {
-			let res = Self::retrieve_utxo(source, block_cache, scid).await;
+			let res = Self::retrieve_utxo(source, txid_cache, scid).await;
 			fut.resolve(res);
 		});
 		UtxoResult::Async(res)

### lightning-block-sync/src/rest.rs
@@ -6,8 +6,8 @@ use crate::gossip::UtxoSource;
 use crate::http::{BinaryResponse, HttpClient, HttpClientError, JsonResponse, ToParseErrorMessage};
 use crate::{BlockData, BlockHeaderData, BlockSource, BlockSourceResult};
 
-use bitcoin::hash_types::BlockHash;
-use bitcoin::OutPoint;
+use bitcoin::hash_types::{BlockHash, Txid};
+use bitcoin::{OutPoint, TxOut};
 
 use std::convert::TryFrom;
 use std::convert::TryInto;
@@ -77,15 +77,24 @@ impl UtxoSource for RestClient {
 		}
 	}
 
-	fn is_output_unspent<'a>(
+	fn get_block_txids<'a>(
+		&'a self, block_hash: &'a BlockHash,
+	) -> impl Future<Output = BlockSourceResult<Vec<Txid>>> + Send + 'a {
+		async move {
+			let resource_path = format!("block/notxdetails/{}.json", block_hash.to_string());
+			Ok(self.request_resource::<JsonResponse, _>(&resource_path).await?)
+		}
+	}
+
+	fn get_unspent_txout<'a>(
 		&'a self, outpoint: OutPoint,
-	) -> impl Future<Output = BlockSourceResult<bool>> + Send + 'a {
+	) -> impl Future<Output = BlockSourceResult<Option<TxOut>>> + Send + 'a {
 		async move {
 			let resource_path =
 				format!("getutxos/{}-{}.json", outpoint.txid.to_string(), outpoint.vout);
 			let utxo_result =
 				self.request_resource::<JsonResponse, GetUtxosResponse>(&resource_path).await?;
-			Ok(utxo_result.hit_bitmap_nonempty)
+			Ok(utxo_result.utxo)
 		}
 	}
 }
@@ -151,21 +160,40 @@ mod tests {
 		let client = RestClient::new(server.endpoint());
 
 		let outpoint = OutPoint::new(bitcoin::Txid::from_byte_array([0; 32]), 0);
-		let unspent_output = client.is_output_unspent(outpoint).await.unwrap();
-		assert_eq!(unspent_output, false);
+		let unspent_output = client.get_unspent_txout(outpoint).await.unwrap();
+		assert_eq!(unspent_output, None);
 	}
 
 	#[tokio::test]
 	async fn parses_positive_getutxos() {
 		let server = HttpServer::responding_with_ok(MessageBody::Content(
 			// A real response contains lots more data, but we actually only look at the "bitmap"
-			// field, so this should suffice for testing
-			"{\"chainHeight\": 1, \"bitmap\":\"1\",\"utxos\":[]}",
+			// and "utxos" fields, so this should suffice for testing
+			"{\"chainHeight\": 1, \"bitmap\":\"1\",\"utxos\":
+				[{\"height\": 1, \"value\": 0.07, \"scriptPubKey\": {\"hex\": \"0014abcd\"}}]}",
 		));
 		let client = RestClient::new(server.endpoint());
 
 		let outpoint = OutPoint::new(bitcoin::Txid::from_byte_array([0; 32]), 0);
-		let unspent_output = client.is_output_unspent(outpoint).await.unwrap();
-		assert_eq!(unspent_output, true);
+		let unspent_output = client.get_unspent_txout(outpoint).await.unwrap();
+		let expected = TxOut {
+			value: bitcoin::Amount::from_sat(7_000_000),
+			script_pubkey: bitcoin::ScriptBuf::from_hex("0014abcd").unwrap(),
+		};
+		assert_eq!(unspent_output, Some(expected));
+	}
+
+	#[tokio::test]
+	async fn parses_block_txids() {
+		let txid = bitcoin::Txid::from_byte_array([1; 32]);
+		let server = HttpServer::responding_with_ok(MessageBody::Content(format!(
+			"{{\"nTx\": 1, \"tx\": [\"{}\"]}}",
+			txid
+		)));
+		let client = RestClient::new(server.endpoint());
+
+		let block_hash = BlockHash::from_byte_array([0; 32]);
+		let txids = client.get_block_txids(&block_hash).await.unwrap();
+		assert_eq!(txids, vec![txid]);
 	}
 }

### lightning-block-sync/src/rpc.rs
@@ -5,8 +5,8 @@ use crate::gossip::UtxoSource;
 use crate::http::{HttpClient, HttpClientError, JsonResponse, ToParseErrorMessage};
 use crate::{BlockData, BlockHeaderData, BlockSource, BlockSourceResult};
 
-use bitcoin::hash_types::BlockHash;
-use bitcoin::OutPoint;
+use bitcoin::hash_types::{BlockHash, Txid};
+use bitcoin::{OutPoint, TxOut};
 
 use serde_json;
 
@@ -190,16 +190,24 @@ impl UtxoSource for RpcClient {
 		}
 	}
 
-	fn is_output_unspent<'a>(
+	fn get_block_txids<'a>(
+		&'a self, block_hash: &'a BlockHash,
+	) -> impl Future<Output = BlockSourceResult<Vec<Txid>>> + Send + 'a {
+		async move {
+			let header_hash = serde_json::json!(block_hash.to_string());
+			let verbosity = serde_json::json!(1);
+			Ok(self.call_method("getblock", &[header_hash, verbosity]).await?)
+		}
+	}
+
+	fn get_unspent_txout<'a>(
 		&'a self, outpoint: OutPoint,
-	) -> impl Future<Output = BlockSourceResult<bool>> + Send + 'a {
+	) -> impl Future<Output = BlockSourceResult<Option<TxOut>>> + Send + 'a {
 		async move {
 			let txid_param = serde_json::json!(outpoint.txid.to_string());
 			let vout_param = serde_json::json!(outpoint.vout);
 			let include_mempool = serde_json::json!(false);
-			let utxo_opt: serde_json::Value =
-				self.call_method("gettxout", &[txid_param, vout_param, include_mempool]).await?;
-			Ok(!utxo_opt.is_null())
+			Ok(self.call_method("gettxout", &[txid_param, vout_param, include_mempool]).await?)
 		}
 	}
 }
@@ -322,17 +330,37 @@ mod tests {
 		let server = HttpServer::responding_with_ok(MessageBody::Content(response));
 		let client = RpcClient::new(CREDENTIALS, server.endpoint());
 		let outpoint = OutPoint::new(bitcoin::Txid::from_byte_array([0; 32]), 0);
-		let unspent_output = client.is_output_unspent(outpoint).await.unwrap();
-		assert_eq!(unspent_output, false);
+		let unspent_output = client.get_unspent_txout(outpoint).await.unwrap();
+		assert_eq!(unspent_output, None);
 	}
 
 	#[tokio::test]
 	async fn fetches_utxo() {
-		let response = serde_json::json!({ "result": {"bestblock": 1, "confirmations": 42}});
+		let response = serde_json::json!({ "result": {
+			"bestblock": 1,
+			"confirmations": 42,
+			"value": 0.07,
+			"scriptPubKey": { "hex": "0014abcd" },
+		}});
 		let server = HttpServer::responding_with_ok(MessageBody::Content(response));
 		let client = RpcClient::new(CREDENTIALS, server.endpoint());
 		let outpoint = OutPoint::new(bitcoin::Txid::from_byte_array([0; 32]), 0);
-		let unspent_output = client.is_output_unspent(outpoint).await.unwrap();
-		assert_eq!(unspent_output, true);
+		let unspent_output = client.get_unspent_txout(outpoint).await.unwrap();
+		let expected = TxOut {
+			value: bitcoin::Amount::from_sat(7_000_000),
+			script_pubkey: bitcoin::ScriptBuf::from_hex("0014abcd").unwrap(),
+		};
+		assert_eq!(unspent_output, Some(expected));
+	}
+
+	#[tokio::test]
+	async fn fetches_block_txids() {
+		let txid = bitcoin::Txid::from_byte_array([1; 32]);
+		let response = serde_json::json!({ "result": { "nTx": 1, "tx": [txid.to_string()] }});
+		let server = HttpServer::responding_with_ok(MessageBody::Content(response));
+		let client = RpcClient::new(CREDENTIALS, server.endpoint());
+		let block_hash = BlockHash::from_byte_array([0; 32]);
+		let txids = client.get_block_txids(&block_hash).await.unwrap();
+		assert_eq!(txids, vec![txid]);
 	}
 }

### pending_changelog/4846-getblock-gossip-verification.txt
@@ -0,0 +1,9 @@
+# API Updates
+
+ * `lightning-block-sync`'s `UtxoSource` trait now fetches block txid lists
+   (via `UtxoSource::get_block_txids`) rather than full blocks when verifying
+   gossip against the chain, and `UtxoSource::is_output_unspent` was replaced
+   by `UtxoSource::get_unspent_txout`, which additionally returns the output
+   itself. This reduces the bandwidth required to validate network graph
+   when using Bitcoin Core as a chain source. Custom implementations of
+	 `UtxoSource` must implement the new methods.