If you're implementing this manually (presumably to improve error handling) I suggest to use size hint both to pre-allocate the vec and to return early.

And we should use Error::invalid_length instead of custom.

Implementing it automatically with #[serde(into = "Vec<sha256::Hash>")]

I think the optimizer will see you're comparing twice and remove the duplicate, so the commit message is not accurate, the only cost is returning the extra bool. Or if you want to be explicit assign a < b to a variable and use it at both places.

Seeing these panics, why are we even storing TaprootBuilder and not NodeInfo and script leaves? Make invalid states unrepresentable...

Indeed, I already am working on this locally. Raised this PR initially to move things forward.

Since serialize accepts &self this is forced to clone. I think into shouldn't be needed since serde treats newtypes as transparent.

It does not. It is still serialized as a new struct. Removing this line results in

thread 'taproot::test::test_merkle_branch_serde' panicked at 'expected Token::Seq { len: Some(2) } but serialized as NewtypeStruct { name: "TaprootMerkleBranch", }

Oh, yeah, serializers should treat it as transaparent but they don't have to. Maybe #[serde(transparent)] would work? I'm not sure if it'd clash with try_from though.

Yeah, #[serde(transparent)] conflicts with try_from

Why these two delegate to a different field? It looks foot-gunny since they are supposed to be related.

Perhaps, I should add some documentation to this. For taproot trees, because the leaves get sorted by hash while constructing the root, a tree with root A, left child B and right child C is the same as root A with left child B and right child A.

We had Eq reflect this property in TapTree, so I thought Hash should reflect this property. The Eq property is really handy while round-tripping psbts.

If Eq returns true then comparing hashes must also return true.

I'm confused by this explanation:

a tree with root A, left child B and right child C is the same as root A with left child B and right child A.

Maybe you meant to say this?

a tree with root A, left child B and right child C is the same as root A with left child C and right child B.

Sorry, that is what I meant to say. This is reason for custom implementation of Eq and Hash in NodeInfo. But TapTree now auto drives it.

? There's no panic here.

Empty line

Would it make sense to have fn with_capacity(capacity: usize) -> TaprootBuilder and call it here? I suppose we would need to internally allocate Vec with log2(capacity + 1) (size_of::<usize>() * 8 - (capacity + 1).leading_zeros() if I'm not mistaken)

I did not follow the formula, but conceptually I don't think it is possible to estimate the height of a tree from the number of leaves.
For example, there can be 128 depth tree with 129 leaves. One leaf at each level and 2 leaves at level 128.

I don't think we have to optimize for unoptimal trees - they will have bigger problems than a vec reallocating too many times.

Ah right. capacity is just a good enough guess, does not have to be strict upper bound.

Done. I don't think there is a +1 here. Used size_of::<usize>() * 8 - (capacity).leading_zeros() instead of capacity + 1

Looks like outside code could break invariants when this is pub?

Indeed, it might break invariants. I remember thinking about this while adding pub, but I was mistaken :(

If the leaf is not known we already know the hash and should return it?

I thought it might be confusing because the hidden node might not necessarily be a leaf. It could be a hidden tree.

I had a note for adding node_hash() method that returns the TapNodeHash

Ah, that makes sense. Agree with adding node_hash.

This doesn't look correct, the value needs to be number of bytes but len() is returning number of items.

Perhaps unreachable! rather than silently ignoring potential bug?

This is not a bug. TaprootSpendInfo is a cached data structure for storing information about spending leaves. As of now, we don't cache anything for hidden leaves.

Perhaps this is cleaner:

    pub fn from_node_info<C: secp256k1::Verification>(
        secp: &Secp256k1<C>,
        internal_key: UntweakedPublicKey,
        node: NodeInfo,
    ) -> TaprootSpendInfo {
        // Create as if it is a key spend path with the given merkle root
        let root_hash = Some(node.hash);
        let mut info = TaprootSpendInfo::new_key_spend(secp, internal_key, root_hash);

        for leaves in node.leaves {
            match leaves.leaf {
                TapLeaf::Hidden(_) => {
                    // We don't store any information about hidden nodes in TaprootSpendInfo.
                }
                TapLeaf::Script(script, ver) => {
                    let key = (script, ver);
                    let value = leaves.merkle_branch;
                    match info.script_map.get_mut(&key) {
                        None => {
                            let mut set = BTreeSet::new();
                            set.insert(value);
                            info.script_map.insert(key, set);
                        },
                        Some(set) => {
                            set.insert(value);
                        }
                    }
                },
            }
        }
        info
    }

I think this needs to be multiplied by 2 since there are two calls of serialize_element.

good catch

x needs to be divided by 2.

Oh, just realized this is wrong because it has to forward size_hint correctly. This method also doesn't need to be implemented.

Missing size_hint.

Other traits for consideration here and above: FusedIterator, DoubleEndedIterator

Perhaps this is cleaner:

    pub fn from_node_info<C: secp256k1::Verification>(
        secp: &Secp256k1<C>,
        internal_key: UntweakedPublicKey,
        node: NodeInfo,
    ) -> TaprootSpendInfo {
        // Create as if it is a key spend path with the given merkle root
        let root_hash = Some(node.hash);
        let mut info = TaprootSpendInfo::new_key_spend(secp, internal_key, root_hash);

        for leaves in node.leaves {
            match leaves.leaf {
                TapLeaf::Hidden(_) => {
                    // We don't store any information about hidden nodes in TaprootSpendInfo.
                }
                TapLeaf::Script(script, ver) => {
                    let key = (script, ver);
                    let value = leaves.merkle_branch;
                    match info.script_map.get_mut(&key) {
                        None => {
                            let mut set = BTreeSet::new();
                            set.insert(value);
                            info.script_map.insert(key, set);
                        },
                        Some(set) => {
                            set.insert(value);
                        }
                    }
                },
            }
        }
        info
    }

OT: These use self::<ErrorType>::* statements are sprinkled around the codebase because I was coding sometime with only half my brain connected, the self:: is totally useless.

Why the * 32 when we push just the length here?

another good catch. I really need to think before I am typing :(

Its not important right now but just FYI; we don't need the : here.

nit: And here.

Any reason next get inlined but not size_hint?