lol. concept ACK.

I think if we ever hit four, then we should just give in and have a Vec of indices, which would at least be much cheaper than having a Vec<Vec<u8>>. But given the slowness of bitcoin and the general nature of the annex, I'll bet that we don't hit four for many years.

I was also debating adding a small helper method for getting the byte slice of the tapscript as an Option.

It would basically be:

if w.len() >= 2 && w.last().get(0)? == &0x50 { w.third_to_last() } else { w.second_to_last() }

Whether or not the Witness stack is actually p2tr or not, we don't know, so just blindly follow the BIP. The caller will have to ensure they only call it on a p2tr Witness stack.

Thoughts?

Not opposed to caching another index but the API is starting to look ridiculous. You know, there is this thing called an array that allows you to reference multiple items by a number. :)

I suggest having a single field indices_cache storing the indices. Then instead of having whatever_to_last specialize nth(), last() on the iterator to use the cache and document this property.

If witness.iter().last() looks too scary because of apparent iteration we can also have nth method directly but I'm not sure how much it'll help.

Also agree fully with looking into having Vec if there are many elements - I'd still like to cache common sizes without allocation though.

Concept ACK adding helper method for tapscript.

The caller will have to ensure they only call it on a p2tr Witness stack.

We don't know because we would have to know the script_pubkey of previous transaction so validating this is impossible right?

I suggest having a single field indices_cache storing the indices.

This would be the correct way to do it. I would like to see what @RCasatta thinks as he originally authored the new Witness struct.

I didn't know what to say because I didn't like the API and neither adding indices_cache because it will require other allocations impacting deserializing performance.

But I think we can have a nicer API without impacting performance!

We can add the indexes at the beginning of the content field as fixed-size integers (I think u32 since u32::MAX>MAX_VEC_SIZE).

When deserializing, the number of elements in the witness is known at the beginning so we can skip the first size(u32)*witness_elements bytes of content and fill it while deserializing the elements. The current initial size of content (128) should still be enough to accommodate more than 75% of witnesses in mainnet but this should be double-checked.

When serializing, after encoding the witness_elements varint we can simply skip the first size(u32)*witness_elements bytes of content.

At this point, we can implement an efficient Index (and also first() last() and nth()) by doing a lookup in the indexes at the beginning of content like index = u32::from_xx_bytes( content[i * size(u32)] ) as usize
The index points at the ith element before the varint storing the length, once the length is read we have the start and end of the slice of the requested witness element.

We don't know because we would have to know the script_pubkey of previous transaction so validating this is impossible right?

What I meant was, we assume the caller to have all the external info available to discern that this is p2tr. This includes the script_pubkey of the prev_out.

Neat. It took me a moment to understand what you're saying @RCasatta but I like it. Basically we widen the allocation during deserialization and copy each witness element's length prefix into the extra area where it can be efficiently indexed into.

I have tried implementing @RCasatta idea and one issue that is a bit hairy I found is the push() method.

If we have the indices at the beginning of the content, we'll need to slide everything to the right to make room for the new u32 at the beginning, and all the indices already encoded previously will need to be updated by +4.

If we have indices at the end of the content, it'll be harder to deterministically find the index without knowing the total size of the actual content.

Perhaps having the indices at the end, and include a new usize in the struct that points to the beginning of the indices?

I don't think we should have a push method on this type. If you want to modify it you should have to convert to a Vec<Vec<u8>> and back.

Perhaps the indexing fix with push() removed can land in a future breaking version update.

Any objections to merging this as-is for now? Or does anyone else want to take a crack at adding the indexing with push() present?

I'll also add the helper method for getting the tapscript.

How about adding the indices at the end? It'll still require moving things around during push but not updating the indices and there will be generally less bytes to move. It still needs to be documented as somewhat slow but people should already expect at least allocations from push. We could optimize it by providing some reserve API.

Any objections to merging this as-is for now?

Adding APIs that will be removed in the future is not nice. I suggest you add nth(n: usize) method and then conditionally iterate or not, hiding the cache. If we implement @RCasatta suggestion we will keep it and just change the implementation.

I wouldn't mind having a push method, especially since we already have one, but it does seem like extra work and complexity for a niche feature. (Usually Witnesses are constructed in one shot from a Vec<Vec<u8>> and converted, or parsed from a transaction and never changed.)

OTOH it would be remarkably easy to fuzz this against the push-to-Vec<Vec<u8>> strategy so I'm not too worried about bugs.

TODO:

• Fix fuzzer errors (le bytes vs ne bytes?)
• Write tests for get_tapscript

Usually Witnesses are constructed in one shot from a Vec<Vec<u8>>

I never implemented it myself but I'd expect at least some people would like to collect an iterator or something else that makes fewer allocations.

I'm assuming the fuzzer errors mean my logic is causing a panic instead of handling garbage input gracefully...

I'll have to look over the changes again. If anyone has time to review I'd appreciate it.

Thanks.

Not sure why the fuzzer is failing... I have no clue how to read the output.

I am assuming there's some sort of panic when the deserializer is fed garbage.

CI shows compile errors though.

These are unrelated to the PR. Probably need to rebase for some reason...?

Looks like master merged some changes to the test suite...................... not sure how/why that would affect this branch though...?

Looks like incorrect imports in bitcoin/examples/taproot-psbt.rs

See #1345

FYI, the nightly CI fail (due to benches failing) is unrelated to this PR - I'm investigating it.

Nightly bug is fixed now.

All tests are passing.

Please review when you have the time. Thanks!

Thanks for your contribution @junderw. This PR is hard to review because there are patches later in the series that change code written earlier in the series, worse still, one patch changes ne -> le then a later patch changes le -> ne and neither patches has any justification as to why the change is being made. Can you please squash this PR down in to a set of patches that each do a single thing with description in each patch of whats being done and why - otherwise it is very hard to work out if I should ack or not.

Sorry to be a pain.

Thanks @tcharding I have separated it into two different patches. The index patch was fairly intertwined. Perhaps I could have teased out Index<usize>, but it was a small enough diff and is basically a simple wrapper around nth(usize), so I left it in.

You legend, thanks a lot man you went above and beyond, that was super nice to review!

utACK (will ACK for real once my tests finish). This looks great! My comments are only nits.

Some of these new functions are great candidates for property testing, a la #1370.

I will make another PR fixing the nits later.

Thanks!

I'll merge this. Nits can be addressed in a later PR.