p2p: add BlockLocator newtype with logarithmic build

diff --git a/p2p/src/message.rs b/p2p/src/message.rs
index 1bcd5a9b..5162f563 100644
--- a/p2p/src/message.rs
+++ b/p2p/src/message.rs
@@ -1936,7 +1936,7 @@ mod test {
     use super::*;
     use crate::address::AddrV2;
     use crate::bip152::BlockTransactionsRequest;
-    use crate::message_blockdata::{GetBlocksMessage, GetHeadersMessage, Inventory};
+    use crate::message_blockdata::{BlockLocator, GetBlocksMessage, GetHeadersMessage, Inventory};
     use crate::message_bloom::{BloomFlags, FilterAdd, FilterLoad};
     use crate::message_compact_blocks::SendCmpct;
     use crate::message_filter::{
@@ -1976,18 +1976,18 @@ mod test {
             NetworkMessage::NotFound(InventoryPayload(vec![Inventory::Error([0u8; 32])])),
             NetworkMessage::GetBlocks(GetBlocksMessage {
                 version: ProtocolVersion::from_nonstandard(70001),
-                locator_hashes: vec![
+                locator_hashes: BlockLocator::from(vec![
                     BlockHash::from_byte_array(hash([1u8; 32]).to_byte_array()),
                     BlockHash::from_byte_array(hash([4u8; 32]).to_byte_array()),
-                ],
+                ]),
                 stop_hash: BlockHash::from_byte_array(hash([5u8; 32]).to_byte_array()),
             }),
             NetworkMessage::GetHeaders(GetHeadersMessage {
                 version: ProtocolVersion::from_nonstandard(70001),
-                locator_hashes: vec![
+                locator_hashes: BlockLocator::from(vec![
                     BlockHash::from_byte_array(hash([10u8; 32]).to_byte_array()),
                     BlockHash::from_byte_array(hash([40u8; 32]).to_byte_array()),
-                ],
+                ]),
                 stop_hash: BlockHash::from_byte_array(hash([50u8; 32]).to_byte_array()),
             }),
             NetworkMessage::MemPool,
diff --git a/p2p/src/message_blockdata.rs b/p2p/src/message_blockdata.rs
index 4c2b34a7..60a588ef 100644
--- a/p2p/src/message_blockdata.rs
+++ b/p2p/src/message_blockdata.rs
@@ -194,6 +194,146 @@ impl std::error::Error for InventoryDecoderError {
     fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
 }
 
+/// A block locator.
+///
+/// Maximum number of hashes in a block locator, matching Bitcoin Core's `MAX_LOCATOR_SZ`.
+pub const MAX_LOCATOR_HASHES: usize = 101;
+
+/// An ordered list of block hashes from newest to oldest. Used in `getblocks` and
+/// `getheaders` messages to help a peer find the most recent common block.
+#[derive(PartialEq, Eq, Clone, Debug, Default)]
+pub struct BlockLocator(Vec<BlockHash>);
+
+impl BlockLocator {
+    /// Returns the locator hashes, ordered newest to oldest.
+    pub fn hashes(&self) -> &[BlockHash] { &self.0 }
+
+    /// Constructs a block locator for the given chain tip.
+    ///
+    /// `get_ancestor(h)` must return the block hash at height `h` on the best chain.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if `get_ancestor` returns an error.
+    pub fn build<F, E>(tip_height: u32, mut get_ancestor: F) -> Result<Self, E>
+    where
+        F: FnMut(u32) -> Result<BlockHash, E>,
+    {
+        let mut hashes = Vec::with_capacity(MAX_LOCATOR_HASHES);
+        let mut step: u32 = 1;
+        let mut height = tip_height;
+
+        loop {
+            hashes.push(get_ancestor(height)?);
+            if height == 0 || hashes.len() >= MAX_LOCATOR_HASHES {
+                break;
+            }
+            height = height.saturating_sub(step);
+            if hashes.len() > 10 {
+                step = step.saturating_mul(2);
+            }
+        }
+
+        Ok(Self(hashes))
+    }
+}
+
+impl From<Vec<BlockHash>> for BlockLocator {
+    fn from(hashes: Vec<BlockHash>) -> Self { Self(hashes) }
+}
+
+impl From<BlockLocator> for Vec<BlockHash> {
+    fn from(locator: BlockLocator) -> Self { locator.0 }
+}
+
+impl Encodable for BlockLocator {
+    #[inline]
+    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
+        self.0.consensus_encode(w)
+    }
+}
+
+impl Decodable for BlockLocator {
+    #[inline]
+    fn consensus_decode<R: BufRead + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
+        Ok(Self(Decodable::consensus_decode(r)?))
+    }
+}
+
+type BlockLocatorInnerEncoder<'e> = Encoder2<CompactSizeEncoder, SliceEncoder<'e, BlockHash>>;
+
+encoding::encoder_newtype! {
+    /// The encoder for [`BlockLocator`].
+    pub struct BlockLocatorEncoder<'e>(BlockLocatorInnerEncoder<'e>);
+}
+
+impl encoding::Encodable for BlockLocator {
+    type Encoder<'e> = BlockLocatorEncoder<'e>;
+
+    fn encoder(&self) -> Self::Encoder<'_> {
+        BlockLocatorEncoder::new(Encoder2::new(
+            CompactSizeEncoder::new(self.0.len()),
+            SliceEncoder::without_length_prefix(&self.0),
+        ))
+    }
+}
+
+type BlockLocatorInnerDecoder = VecDecoder<BlockHash>;
+
+/// The decoder for the [`BlockLocator`] type.
+pub struct BlockLocatorDecoder(BlockLocatorInnerDecoder);
+
+impl BlockLocatorDecoder {
+    /// Creates a new decoder.
+    pub fn new() -> Self { Self(VecDecoder::<BlockHash>::new()) }
+}
+
+impl Default for BlockLocatorDecoder {
+    fn default() -> Self { Self::new() }
+}
+
+impl encoding::Decoder for BlockLocatorDecoder {
+    type Output = BlockLocator;
+    type Error = BlockLocatorDecoderError;
+
+    #[inline]
+    fn push_bytes(&mut self, bytes: &mut &[u8]) -> Result<bool, Self::Error> {
+        self.0.push_bytes(bytes).map_err(BlockLocatorDecoderError)
+    }
+
+    #[inline]
+    fn end(self) -> Result<Self::Output, Self::Error> {
+        Ok(BlockLocator(self.0.end().map_err(BlockLocatorDecoderError)?))
+    }
+
+    #[inline]
+    fn read_limit(&self) -> usize { self.0.read_limit() }
+}
+
+impl encoding::Decodable for BlockLocator {
+    type Decoder = BlockLocatorDecoder;
+    fn decoder() -> Self::Decoder { BlockLocatorDecoder::new() }
+}
+
+/// An error consensus decoding a [`BlockLocator`].
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct BlockLocatorDecoderError(<BlockLocatorInnerDecoder as encoding::Decoder>::Error);
+
+impl From<Infallible> for BlockLocatorDecoderError {
+    fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl fmt::Display for BlockLocatorDecoderError {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write_err!(f, "block locator error"; self.0)
+    }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for BlockLocatorDecoderError {
+    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> { Some(&self.0) }
+}
+
 // Some simple messages
 
 /// The `getblocks` message
@@ -201,10 +341,8 @@ impl std::error::Error for InventoryDecoderError {
 pub struct GetBlocksMessage {
     /// The protocol version
     pub version: ProtocolVersion,
-    /// Locator hashes --- ordered newest to oldest. The remote peer will
-    /// reply with its longest known chain, starting from a locator hash
-    /// if possible and block 1 otherwise.
-    pub locator_hashes: Vec<BlockHash>,
+    /// Block locator --- ordered newest to oldest.
+    pub locator_hashes: BlockLocator,
     /// References the block to stop at, or zero to just fetch the maximum 500 blocks
     pub stop_hash: BlockHash,
 }
@@ -214,17 +352,15 @@ pub struct GetBlocksMessage {
 pub struct GetHeadersMessage {
     /// The protocol version
     pub version: ProtocolVersion,
-    /// Locator hashes --- ordered newest to oldest. The remote peer will
-    /// reply with its longest known chain, starting from a locator hash
-    /// if possible and block 1 otherwise.
-    pub locator_hashes: Vec<BlockHash>,
+    /// Block locator --- ordered newest to oldest.
+    pub locator_hashes: BlockLocator,
     /// References the header to stop at, or zero to just fetch the maximum 2000 headers
     pub stop_hash: BlockHash,
 }
 
 type GetBlocksOrHeadersInnerEncoder<'e> = Encoder3<
     ProtocolVersionEncoder<'e>,
-    Encoder2<CompactSizeEncoder, SliceEncoder<'e, BlockHash>>,
+    BlockLocatorEncoder<'e>,
     BlockHashEncoder<'e>,
 >;
 
@@ -247,10 +383,7 @@ impl encoding::Encodable for GetHeadersMessage {
     fn encoder(&self) -> Self::Encoder<'_> {
         GetHeadersEncoder::new(Encoder3::new(
             self.version.encoder(),
-            Encoder2::new(
-                CompactSizeEncoder::new(self.locator_hashes.len()),
-                SliceEncoder::without_length_prefix(&self.locator_hashes),
-            ),
+            self.locator_hashes.encoder(),
             self.stop_hash.encoder(),
         ))
     }
@@ -265,17 +398,14 @@ impl encoding::Encodable for GetBlocksMessage {
     fn encoder(&self) -> Self::Encoder<'_> {
         GetBlocksEncoder::new(Encoder3::new(
             self.version.encoder(),
-            Encoder2::new(
-                CompactSizeEncoder::new(self.locator_hashes.len()),
-                SliceEncoder::without_length_prefix(&self.locator_hashes),
-            ),
+            self.locator_hashes.encoder(),
             self.stop_hash.encoder(),
         ))
     }
 }
 
 type GetBlocksOrHeadersInnerDecoder =
-    Decoder3<ProtocolVersionDecoder, VecDecoder<BlockHash>, BlockHashDecoder>;
+    Decoder3<ProtocolVersionDecoder, BlockLocatorDecoder, BlockHashDecoder>;
 
 /// Decoder type for [`GetBlocksMessage`].
 pub struct GetBlocksMessageDecoder(GetBlocksOrHeadersInnerDecoder);
@@ -328,7 +458,7 @@ impl encoding::Decodable for GetBlocksMessage {
     fn decoder() -> Self::Decoder {
         GetBlocksMessageDecoder(Decoder3::new(
             ProtocolVersionDecoder::new(),
-            VecDecoder::<BlockHash>::new(),
+            BlockLocatorDecoder::new(),
             BlockHashDecoder::new(),
         ))
     }
@@ -339,7 +469,7 @@ impl encoding::Decodable for GetHeadersMessage {
     fn decoder() -> Self::Decoder {
         GetHeadersMessageDecoder(Decoder3::new(
             ProtocolVersionDecoder::new(),
-            VecDecoder::<BlockHash>::new(),
+            BlockLocatorDecoder::new(),
             BlockHashDecoder::new(),
         ))
     }
@@ -391,12 +521,19 @@ impl_consensus_encoding!(GetBlocksMessage, version, locator_hashes, stop_hash);
 
 impl_consensus_encoding!(GetHeadersMessage, version, locator_hashes, stop_hash);
 
+#[cfg(feature = "arbitrary")]
+impl<'a> Arbitrary<'a> for BlockLocator {
+    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+        Ok(Self::from(Vec::<BlockHash>::arbitrary(u)?))
+    }
+}
+
 #[cfg(feature = "arbitrary")]
 impl<'a> Arbitrary<'a> for GetHeadersMessage {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
         Ok(Self {
             version: u.arbitrary()?,
-            locator_hashes: Vec::<BlockHash>::arbitrary(u)?,
+            locator_hashes: u.arbitrary()?,
             stop_hash: u.arbitrary()?,
         })
     }
@@ -407,7 +544,7 @@ impl<'a> Arbitrary<'a> for GetBlocksMessage {
     fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
         Ok(Self {
             version: u.arbitrary()?,
-            locator_hashes: Vec::<BlockHash>::arbitrary(u)?,
+            locator_hashes: u.arbitrary()?,
             stop_hash: u.arbitrary()?,
         })
     }
@@ -445,8 +582,8 @@ mod tests {
         assert!(decode.is_ok());
         let real_decode = decode.unwrap();
         assert_eq!(real_decode.version.0, 70002);
-        assert_eq!(real_decode.locator_hashes.len(), 1);
-        assert_eq!(serialize(&real_decode.locator_hashes[0]), genhash);
+        assert_eq!(real_decode.locator_hashes.hashes().len(), 1);
+        assert_eq!(serialize(&real_decode.locator_hashes.hashes()[0]), genhash);
         assert_eq!(real_decode.stop_hash, BlockHash::GENESIS_PREVIOUS_BLOCK_HASH);
 
         assert_eq!(serialize(&real_decode), from_sat);
@@ -461,8 +598,8 @@ mod tests {
         assert!(decode.is_ok());
         let real_decode = decode.unwrap();
         assert_eq!(real_decode.version.0, 70002);
-        assert_eq!(real_decode.locator_hashes.len(), 1);
-        assert_eq!(serialize(&real_decode.locator_hashes[0]), genhash);
+        assert_eq!(real_decode.locator_hashes.hashes().len(), 1);
+        assert_eq!(serialize(&real_decode.locator_hashes.hashes()[0]), genhash);
         assert_eq!(real_decode.stop_hash, BlockHash::GENESIS_PREVIOUS_BLOCK_HASH);
 
         assert_eq!(serialize(&real_decode), from_sat);