Huffman Chapter Completed.

jachiang commented 5 years ago

Resolves: #54

jachiang commented 5 years ago

Have incorporated @jnewbery feedback, thank you!

jnewbery commented 5 years ago

Thanks for addressing my feedback!

I think it'd be useful to explain more concretely what the weight function is. We're trying to minimize the expected size of the transaction, so I think it's something like:

probability of script being used x total size of witness spending script

Is that right?

jachiang commented 5 years ago

Thanks for the comments and improvements @bitschmidty @jnewbery.

I have incorporated all your suggestions:

Inline comments from bitschmidty.
Better explanation of the goal: Minimize expected witness weight during script path spend.
Replaced original exercise (height inferred from controlblock) with a probability weight assignment exercise which does not assume knowledge about controlblock.

jnewbery commented 5 years ago

I've merged the first two commits separately and rebased this on master.

jachiang commented 5 years ago

Hmmm, yes perhaps you're right that expected should only be used for the distribution. I think the most accurate term we're looking for is probability-weighted weight, but that sounds a bit clumsy. I've just realised that you're assuming that the tapscript witness is the same weight for all tapscripts in this tree, and I think you're using the word 'weight' lower down in this notebook for 'probability'. Is that correct? If so, I think it's pretty confusing.

Hm, I would suggest the following, let me know if you agree:

"Expected witness weight" = tapscript weights multiplied by probability distribution.
"Assigned frequencies" = Huffman constructor weights.
"Assigned" because their absolute values are arbitrary, it is their ratios which determine the tree structure.
We can now reserve "weight" for witness/tx's.

Regarding varying tapscript witness weights:

In the example, all tapscripts have equal witness weights.
Unless I missed something, they do not necessarily need to be equal, in order for Huffman to reduce the expected (probability-adjusted) witness weight.
A byte saved in the highest probability tapscript spend has the highest savings impact on the overall expected witness weight, regardless of the individual tapscript witness weights.
Do you agree?

jachiang commented 5 years ago

Updated based on @jnewbery's most recent review.

jnewbery commented 5 years ago

Great stuff James. Thanks.

I've squashed in a couple of very small nits.

bitcoinops / taproot-workshop

Huffman Chapter Completed. #124