Restructure motivation/design and add informal summary #871

Includes squashed contributions by GitHub users jonasnick,
real-or-random, AustinWilliams, JustinTArthur, ysangkok,
RCassatta, Sjors, tnakagawa, and guggero.

Clarify what 'reduced' means in tests and use word 'message' instead of 'message hash'

Though perhaps, the emphasis is warranted given its importance. :-)

remove duplicate warning

If we look at

  def IsPayToTaproot(script):
      return len(script) == 35 and script[0] == OP_1 and script[1] == 33 and script[2] >= 0 and script[2] <= 1

First byte is is checked for OP_1. OP_1 is 0x51

But the example code in this BIP returns  

`bytes([0x01, 0x21, output_pubkey[0] & 1]) + output_pubkey[1:]`

First byte 0x01, but it should be 0x51

taproot_output_script: first returned byte should be OP_1 (0x51)

Clarify description of diagram

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Completely switch to 32-byte public keys in bip-schnorr/taproot/tapscript

Clarify how to disable key path spending

Reword 'quadratic residue of...'

Clarify pseudocode of lift_x

Use key path spend terminology more consistently in taproot/tapscript

Use a tagged hash in bip-schnorr nonce derivation

Fix privkey negation in taproot_sign_key

32 byte pubkey nits

Add a footnote about 32-byte security

Rebased by Pieter Wuille

Prescribe that an output key should always have a taproot commitment

Rework Applications section

Move plain public key in output rationale to design section (rebase of #44)

Address some nits

Rebased by Pieter Wuille

Mention SHA256 block size (rebase of #45)

No longer necessary with 32B pubkeys.

bip-taproot: Fix minor grammar issue

Removed reference to 0xc1 leaf version.

Euler's Criterion prime only nit

Remove P2SH support

Rework resource limits section

Move/reword tagged hashes motivation

Fixups

minor wording fixes

Remove 0xc1

Improve readability of bip-taproot wallet section

Link to Schnorr's paper instead of Wikipedia

Accept seckey in the form of bytes and not int in the reference BIP-schnorr code...

Extend codeseparator_position and input_index from 16 to 32 bits

Increase max Merkle path length

Small fix: 0xc1 is possible as first control block byte

Small fixes from review with real-or-random

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Use is_square/is_positive and introduce algorithm names

I'll try to get a link to the CCS paper that does not have a paywall...

bip-schnorr: incorporate results of Neven, Smart, Warinschi

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Explain that MuSig needs key prefixing

Clarify interaction x-only keys with verification

annex is bit 0 of spend_type

Refer to Manuel Fersch's dissertation for provable security of ECDSA. It's freely accessible and multiple results put well in context.

bip-schnorr: Change reference for ECDSA proofs

Improve section on alternatives to OP_CHECKMULTISIG

Explain why CMS is not turned into SUCCESSx

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Co-Authored-By: Tim Ruffing <tim@timruffing.de>

Elaborate on default and alternative signing

Consistently mention resource limits in bip-tapscript

typos

Currently github markdown renders `b''` inside `<source>` tags incorrectly. This makes `h = b''` show as `h = b` and creates some confusion.
The issue can be avoided by using bytes() to create empty byte array

bip-taproot: use bytes() instead of b'' - avoid markdown issue

the final "-None" line in the docstring of `taproot_output_script` example function was actually outside of the docstring

bip-taproot: fix docstring in taproot_output_script

Settle on notation: is_square(y), has_square_y(P)

Adjust reference code and test vectors to latest bip

improve rationale for key prefixing

Fix point_from_bytes accepting out-of-range pubkeys and add test vector

For the key spend the script tree depth is not revealed, it is only done for script spends. This sentence makes sense only for the script spend.

fix: script spend, not key spend reveals tree depth

Link design section of BIP Schnorr in Specification

Internal pubkey calculation fixed in taproot_tweak_pubkey()

Fxied typo in taproot_sign_script()

Fix typo

Per https://github.com/bitcoin/bips/blob/master/bip-0001.mediawiki:

"BIPs may have a Requires header, indicating the BIP numbers that this BIP depends on"

Previously did.

BIP16 has no relation to bip-taproot/tapscript

https://github.com/sipa/bips/pull/135#issuecomment-552754867

- update the paragraph in question to more clearly convey that the helper
  functions, and not the Python3 example code, are from the bip-schnorr
  reference code

- add a link to the reference code in
  https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr/reference.py

Replace R with P in taproot_tweak_seckey

Only first mention of each BIP is made into a link

in addition to `point`. This caused confusion for one reader who expected inclusive at end of range.

remind reader where [:] is defined

Clarify 211 hash bytes and non-reuse of keys

ADD: Require BIPs for Taproot and Tapscript

G refers to the secp256k1 base point rather generator

Add clarification of semantics of 0x00 hash type

Add links to unlinked BIPs

 bip-taproot: clarify bip-schnorr reference code

tapscript: fix minor typo

In this context we are talking about the script branch, not the Merkle tree branch, right? If so, then this should clear things up a little.

make clear it's script branch

Fix typo in schnorr, footnote 2

Thanks to @ajtowns for providing the link

Add missing quote

Throughout the document, elliptic curve multiplication is denoted with dots,
as in `d'⋅G` as opposed to `d'G`.
This is not the case in one place in the 'Default Signing' section,
and one place in 'Adaptor Signatures' section

Missing dots are added for consistency.

Nit: bip-schnorr: Add missing dots that denote multiplication

BIP66 does not mention the inherent ECDSA malleability, but BIP146 does

Rename is_y_square to is_negated in taproot signing

grammar typo fix: inserted "be"

Rephrase "previous design choice" to "list above"

Fix paragraph naming and typo

Add missing closing parenthesis and comma

Replace "both are not" with "neither is"

Nits

Fix footnote 7 and remove references to Euler's criterion

Improve clarity of footnotes for lift_x

Clarify bip-taproot digest difference to bip143 regarding sub-hashes

Mention hash_type malleability would change wtxid

Link to proof sketch of security of implicit Y

Replace signing with signature before validation

fix singular/plural ambiguity

Replace BIP66 link with BIP146

Typo: max bytes hashed for sig is 210

Fix reference formatting

This is supposed to supersede https://github.com/sipa/bips/pull/158.
I tried to say this carefully. I don't think that multiparty signing is in general broken with short hashes. For example the attack in #158 could be avoided by letting everybody not only commit to the nonce but also to the message. It's just that using a collision-resistant hash just eliminates the problem entirely...

Clarify why we don't want short hashes

Replace private key with secret key

Low-S ECDSA is non-malleable under nonstandard assumptions