@dr-orlovsky, I mentioned earlier that this will delay the release even more. Some things like documentation fixes are easy to review, but others take time.

I think I also made a mistake in reviewing #901 (due to a bug in psbt TapTree iterator). TapTree::from_node_info() should also check that there are no hidden leaves in there. This is because serialization of hidden leaves is not supported in psbt, but we can create a builder with hidden leaves. ​

This caused a bug while implementing #901, because here iterator only needs to iterate leaves, but also hidden branches. I repeat some of these things are non-trivial and will take time for careful review.

I don't think any of the above should be required for any use cases. If you want to add op_return commitments, that is already possible using iterator API if we fix it also output the leaf version. I will make a PR to address the bug fixes and constrain the code so that we don't allow hidden branches in this release.

I only think we should restrict ourselves to bug fixes, there should be a code freeze and that is all. People have been waiting for far too long for this release. We will make another release soon after improving the APIs, adding hidden branches.

From my understanding this PR makes iterator better than in the current master. The issues you referenced are unrelated to this PR. I am happy to review your PR fixing hidden branches disallowed in PSBT, but not sure I understand how this can speed up the release.

I am happy to have the release ASAP even without this PR - as much as I am happy to see release cycle not happening once or just twice a year. Please let me know what can I do to speed up this process.

@dr-orlovsky, sorry for being unclear. I was partly frustrated with myself for not catching the bug about hidden branches in the iterator PR. I ended up blaming it on the push for the PR, but I should not have ACKed in rust in the first place.

I think that will considerably change the way the iterator PR #901 should have been done. It was not an issue for Psbt, but the spec does not support hidden branches.

But the goal of the iterator PR was to iterate so that users like you can re-create the same spendinfo using the builder API. However, this is not possible if there are hidden leaves.

builder  = builder.add_hidden(depth, hash);
// But when we iterate using the API, we don't traverse this tree completely because we skip the hidden nodes.

I am happy to have the release ASAP even without this PR

I would like to do this cleanly as follows, but that would change everything in the taproot module. Don't know if we want to do such a change at this point. But without this #901 remains buggy.

// Internally used structure to store information about taproot leaf node
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct LeafInfo {
    // tap leaf (explicit script or hidden)
    pub(crate) tap_leaf : TapLeaf,
    // The merkle proof(hashing partners) to get this node
    pub(crate) merkle_branch: TaprootMerkleBranch,
}

/// Leaves of a taproot tree. Leaves are either the specified with [`Script`] and
/// corresponding [`LeafVersion`] or with a hidden [`TapBranchHash`].
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub(crate) enum TapLeaf {
    /// [`Script`] with it's [`LeafVersion`]
    Script(Script, LeafVersion),
    /// Hidden node with a given [`TapBranchHash`]
    Hidden(TapBranchHash),
}

We have two options:

1. Either change LeafInfo as I suggested above. Note that this will also have to change code to calculate the merkle branches also for hidden nodes.
2. Or remove APIs that allow users to add hidden stuff. That way, we can buy more time and think about this cleanly.

I am leaning towards 2) because 1) will be hard to review quickly and do correctly.

Please let me know what can I do to speed up this process

Regardless of what we do in this PR, I think we should work on a release notes PR/ changelog PR.

@dr-orlovsky, here is something that I think we should end up doing. I don't have my usual setup and am using cafe internet, can't code properly. But here is something rough that I think we should be doing.

Let me know what you about this? sanket1729@a5bd3db. Would it be possible to update this PR so that we do something as suggested there? This was partly my hesitation to ACK this PR

Thank you for explaining details. I am really sorry for missing the part with the hidden branches when I was working on the original iterator implementation.

I think there is a third way of solving this issue: iterator should return Option<Result<LeafInfo>, HiddenBranchError>, and I think this will be both easiest to review and the most correct way of handling hidden branch problem now and in the future. I do not like the idea of extending LeafInfo type such that it can host a branch with TapBranchHash inside: this would be really confusing API. The only way of doing that is to rename LeafInfo into something like LeafBucketInfo and make iterator to explicitly iterate over leafs or hidden branches, and I do not see any reason why it should be made like that, since it clearly looks like a weird workaround.

@sanket1729 Thinking more, I see that the real bug is not the way we iterate TapTree, but the fact that one may create TapTree with hidden leafs. When it will serialize into PSBT, it will skip them and create incorrect representation of the tree, which, when will be signed, result in incorrect signature. So we can't address the problem at the level of iterator.

TapTree with hidden leaves will even fail on roundtrip serialization/deserialization.

So, to address the problem we should introduce TapBuilder::has_hidden_branches and check that in TapTree::from_inner, failing with error on that cases. In this way we will ensure that the TapTree is always correct, can be serialized to PSBT, have a roundtrip serialization and the iterator also will work correctly.

Filed an issue: #928

Ah, sorry @sanket1729, the whole discussion above all is a non-issue: TapTree can't have hidden branches since it will fail on TapTree::from_inner. Thus, the iterator behavior is fully correct. Details: #928 (comment)

We also need to update the iterator to yield hidden nodes.

Sorry, not getting it. We do not have hidden nodes in TapTree.

We do not have hidden nodes in TapTree.

This is a fine solution for now. But eventually(post-release), I think we should have it. When we have it, we cannot use the iterator to re-create taproot trees if there are hidden leaves. The logic with my comment #895 (comment) won't work if there are partial descriptors.

The logic with my comment #895 (comment) won't work if there are partial descriptors.

Unfortunately I found it impossible to make deterministic OP_RETURN commits in the last DFS leaf, since adding a leaf will change ordering of the nodes in the parent and with >80% probability "last" DFS leaf will not be last leaf anymore for a tree with >2 levels.

So I had to change the schema to use the level 0 or level 1 leaf (+proof that the other sibling does not have OP_RETURN commitment). Which required A LOT of coding, re-building the whole tree into a tree-like representation and allowing arbitrary "plastic surgery" on it: https://github.com/LNP-BP/descriptor-wallet/blob/master/scripts/src/taproot.rs

(probably the most interesting part is in tests showcasing the use of the API)
https://github.com/LNP-BP/descriptor-wallet/blob/5aff815aa098fadb89b97aa599c879af28d0a25d/scripts/src/taproot.rs#L857-L904

This is a fine solution for now. But eventually(post-release), I think we should have it. When we have it, we cannot use the iterator to re-create taproot trees if there are hidden leaves.

I see no reason of iterating hidden leafs with the same iterator which iterates the scripts. It can be a separate iterator - and the script iterator must always run only on complete trees (and fail to be constructed on incomplete one). We may have iterator over both (to be able to iterate when not all scripts are known), but this should be a dedicated third iterator.

Unfortunately I found it impossible to make deterministic OP_RETURN commits in the last DFS leaf, since adding a leaf will change ordering of the nodes in the parent and with >80% probability "last" DFS leaf will not be last leaf anymore for a tree with >2 levels.

The last leaf will remain last in the DFS walk no matter what. That is the point of DFS ordering. If you use the algorithm that I mentioned in the comment, it is guaranteed to happen.

To me, the point of the iterator API was so that users could deterministically get the same tree again using the builder.

The last leaf will remain last in the DFS walk no matter what. That is the point of DFS ordering. If you use the algorithm that I mentioned in the comment, it is guaranteed to happen.

Sorry for not explaining properly and messing with DFS: I meant the fact that if you have a partial tree (and in my case for proving the commitment you'd like not to store the whole tree with all the scripts on the client side) you can't prove that the node is last in DFS order and you need the node to be always on the right side of each merkle path to it (in order to be able to prove that there is no alternative commitment in the whole tree) - which is impossible to have. DFS order is simply inapplicable here.

To me, the point of the iterator API was so that users could deterministically get the same tree again using the builder.

Ok, that is a different iterator. The one I need should iterate only through the known scripts.

you can't prove that the node is last in DFS order and you need the node to be always on the right side of each merkle path to it

Yes, you can! Why not? The Merkle proof should not consist of any element that has a hashing partner on the right-hand side? The last node in DSF is guaranteed to be this property.

Yes, you can! Why not? The Merkle proof should not consist of any element that has a hashing partner on the right-hand side? The last node in DSF is guaranteed to be this property.

No, it does not guarantee. I can easily construct the tree where DFS-last node will not be right-hand side in consensus ordering.

I see: https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-8.

This is really what is causing the issue. There is no ordering of leaves guaranteed because multiple trees have the same merkle-root. We cannot assert anything about the position of leaves, we only assert the depth and the that are committed. Now, this seems like a very hard problem to solve.

        //                                       ....
        //                                     /        \
        //                                    /\        /\
        //                                   /  \      /  \
        //                                  A   B     C  / \
        //                                              D   E

Is same as

        //                                       ....
        //                                     /       \
        //                                    /\        /\
        //                                   /  \      /  \
        //                                  A   B    C  / \
        //                                              E   D

Not because of that. There is nothing that will guarantee the hash(AB) < hash(CDE) and hash(C)< hash(DE)

@sanket1729 I have addressed your comments

@sanket1729 thank you for taking your time for all these reviews cycles!

Regarding the name, I thought that when we will add support for the hidden nodes in TapTree, we will add tips() iterator over enum TipNode { ScriptLeaf(ScriptLeaf), Hidden(sha256::Hash) }, and that's why ScriptLeaf makes more sense than LeafInfo.

@Kixunil thank you for reviewing. Since except a single comment these seems to be nits - and I wrote my proposal on the first comment, can we please have this PR merged to get to the taproot release without the need to have next major version right after the release?

I really don't like releasing poorly designed APIs just because of deadline announced a few days ahead. We're not shitcoiners. If we want to compromise then conservatively hiding the type is better compromise because exposing it is semver-compatible, the reverse is not. It's also a trivial change. Note that I'd also suggest being conservative around methods/trait impls. Iterator is obvious, Debug is fine, probably also Clone. For now I'd skip things like ExactSizeIterator because it'd take time to think whether we want to promise them.

Tried to address all your comments, @Kixunil. @sanket1729 this requires your re-ACK, if you have some time

I think @Kixunil's ACK also counts here as this was just a rebase with a minor variable name change from his ACK. This brings us to 3 ACKs and this is the only release-blocking PR.

cc @apoelstra