Blockchain
On Bitcoin’s Schnorr signature algorithm and Taproot script and witness sizes
In a recent article, script and witness sizes for all transaction output types existing as of May 2020 were investigated. This article is…
In a recent article, script and witness sizes for all transaction output types existing as of May 2020 were investigated. This article is a followup that addresses the not yet implemented but highly anticipated PaytoTaproot (P2TR) transaction output type. To this end, the article begins with a discussion of the proposed Schnorr signature algorithm and its use in Taproot and multisignatures in order to provide some context for the data found in P2TR locking scripts and witnesses. Compared to previous work, however, the subsequent investigation of lockingscript and witness sizes is limited to a firstprinciple analysis since empirical data for validation is not yet available.
Formally defined as SegWit version 1 output type in BIP341, the proposed PaytoTaproot (P2TR) output type is meant to improve Bitcoin’s privacy, efficiency, and flexibility. All of these improvements are made possible by a significant extension of Bitcoin’s cryptographic signature system.
At the moment, Bitcoin relies exclusively on the Elliptic Curve Digital Signature Algorithm (ECDSA) for signatures. However, if the proposed Schnorr/Taproot improvements are implemented, this is going to change, and the Elliptic Curve Schnorr Signature Algorithm (ECSSA) will be added to Bitcoin. Although ECSSA offers various advantages over ECDSA, the discussion in this article will address only those that affect scripts and witnesses.
The article starts with a highlevel introduction to the Schnorr signature algorithm. Then, the use of Schnorr in Taproot and proposed Schnorr multisignatures are discussed. Next, the encoding of Schnorr public keys and signatures in Bitcoin is addressed. Finally, Taproot’s lockingscript and witness sizes are analyzed, and the findings summarized in a conclusion.
This section provides a brief overview of Schnorr signature creation and validation and sets the stage for the discussion of Taproot and Schnorr multisignatures in the following sections.
Signature creation
Creating a valid signature for some public key, P, requires the corresponding private key, p, that satisfies P=pG, with G, the generator point of Bitcoin’s elliptic curve secp256k1. Then, given some transaction, m, that spends an output locked with a public key, P, a Schnorr signature is created as follows. First, a random 32byte number, k, is generated. From this k the first part of the signature, a curve point, R, is calculated as R=kG. The second part of the signature, a 32byte value, s, is calculated as s=k+H(R‖P‖m)p
, with k, the previously determined random 32byte number; H, the SHA256 hashing function; R‖P‖m, the concatenation of the previously calculated first part of the signature, R, the public key, P, and the transaction to be signed, m; and, p, the private key. The full signature is then (R, s).
Signature verification
A signature (R, s) is verified by inserting it in the following equation and making sure the equality holds:sG = R+H(R‖P‖m)P
. Note that all of the information required to verify the signature is publicly available: the signature (R, s); the curve’s generator point, G; the SHA256 hashing function, H; the public key, P; and the transaction to be signed, m.
For a valid signature,R=kG and s=k+H(R‖P‖m)p, so the equation becomes(k+H(R‖P‖m)p)G = kG+H(R‖P‖m)P
.
Moreover, because P=pG, the equation can be rewritten as(k+H(R‖P‖m)p)G = kG+H(R‖P‖m)pG
.
Finally, when divided by G, the equation becomesk+H(R‖P‖m)p = k+H(R‖P‖m)p
,
demonstrating that a valid signature can only be created using the private key.
One of the key features of Taproot is that is enables outputs locked with a Schnorr signature to be spent two ways: on one hand, using the key path, in which the output is spent using a Schnorr signature; on the other, using the script path, in which a script and input to it is provided. As a byproduct of this feature, P2TR locking scripts appear identical for PaytoPublicKey and PaytoScriptHash outputs, thereby effectively hiding information about the output’s spending conditions at the time the output is created.
In case of spending by script path, privacy is further enhanced by not revealing scripts that are disjunctions of multiple scripts (i.e., scripts that consist of multiple spending conditions that are combined using the OP_OR
Bitcoin script instruction) in their entirety; instead, only the script that is used to unlock the coins is revealed.
In the following, Taproot’s construction and the resulting implications are discussed in more detail.
Tweaked keys
So far, signature creation and verification used the public and private keys, P and p, where P=pG. To enable Taproot, the private key is tweaked, which means that a value t (called tweak) is added to it. The result is the tweaked private key, q=p+t. The tweak for Taproot defined in BIP341 is t=H(P,S), with H, the SHA256 hashing function; P, the original public key; and, S, the Merkle root of a Merkle tree whose leaves are the scripts that define disjoint spending conditions. From this tweaked private key, q, the tweaked public key, Q, is derived in the usual manner, namely by multiplying the tweaked private key with the generator: Q=qG. The tweaked public key, Q, is then used in the locking scripts of P2TR outputs.
Key path
To spend a P2TR output using the key path, a valid signature for the tweaked public key, Q, is required. This signature can be created using the tweaked private key, q.
Essentially, nothing changes compared to regular Schnorr signature creation. The first part of the signature, R, remains kG. The second part of the signature, s, is determined using the tweaked public and private keys, Q and q, instead of the untweaked counterparts, P and p: s=k+H(R‖Q‖m)q.
Similarly, the verification uses the tweaked public key, Q, so the relevant equation is sG = R+H(R‖Q‖m)Q
.
Inserting the signature yields(k+H(R‖Q‖m)q)G = kG+H(R‖Q‖m)Q
.
Moreover, the public key, Q, is equal to qG, so the equation becomes(k+H(R‖Q‖m)q)G = kG+H(R‖Q‖m)qG
.
Finally, dividing by the curve’s generator point, G, yieldsk+H(R‖Q‖m)q = k+H(R‖Q‖m)q
.
As before, this demonstrates a valid signatures can only be created using the tweaked private key.
Script path
To spend a P2TR output using the script path, the following must be provided: one of the scripts from the Merkle tree whose root, S, was used to calculate the tweak, t; a valid input for the script; the hashes of the missing Merkle tree leaves and branches required to determine the Merkle root, S; and the untweaked public key, P.
In case of the script path, verification consists of two steps. First, by making sure that the tweaked public key used in the locking script, Q, is equal to P+H(P,S)G. Only a valid untweaked public key, P, and Merkle root, S, can fulfill this condition: When substituting qG for Q, the equation becomesqG=P+H(P,S)G
.
Moreover, substituting q for p+t with tweak t=H(P,S), yields(p+H(P,S))G=P+H(P,S)G
.
Next, the terms in parenthesis on the left side of the equation are multiplied with G, so the equation becomespG+H(P,S)G=P+H(P,S)G
.
Finally, P is substituted for pG on the left, which yieldsP+H(P,S)G=P+H(P,S)G
, demonstrating that the equation is satisfied for correct values P and S.
For the previously described verification process, the Merkle root, S, needs to be derived. This is done by hashing the provided script and combining the result with the provided hashes of the missing Merkle tree leaves and branches. All other inputs are directly available: the tweaked public key, Q, is given in the locking script and the untweaked public key, P, is provided along with the script, its input, and the Merkle tree hashes.
The second step in scriptpath verification consists of making sure that the provided inputs fulfill the spending conditions set forth in the script that was presented. If this is the case, verification is successful.
One of the benefits of ECSSA (compared to other signature algorithms such as ECDSA) is its linearity, which refers to the fact that Schnorr’s cryptographic operations are additive and homogeneous. In the following, the concept of additivity and its implications for Schnorr multisignatures are discussed.
Additivity
A function f is considered additive when f(x)+f(y)=f(x+y) for all x and y. This is, for example, the case for a function that multiples its input by ten, f(x)=10x: e.g., f(2)+f(3)=20+30 is that same as f(2+3)=50 (the same is true for all other numbers). A function squaring its inputs, f(x)=x², however, is not additive: e.g., f(2)+f(3)=4+9 is not equal to f(2+3)=25.
The way Schnorr signature’s are constructed makes them additive. In the context of Bitcoin, this leads to some convenient implications, some of which are discussed in the following.
Schnorr multisignatures
The additivity property allows for the creation of a Schnorr multisignature scheme in which a single public key can be used to realize a multisignature requirement. Moreover, a single signature is sufficient to unlock the funds.
A Schnorr multisignature public key, Q, is constructed from multiple individual public keys, Qᵢ: in essence, Q=Q₁+…+Qₙ. A valid Schnorr multisignature, (R, s), for the resulting public key, Q, can be created by combining individual signatures, (Rᵢ, sᵢ), each created using the private key, qᵢ, corresponding to the public key, Qᵢ: in essence, (R=R₁+…+Rₘ, s=s₁+…+sₘ). Note that the actual calculation Q, R, and s is more complex, but the same general idea applies.
This means that independent of m and n, mofn Schnorr multisignatures use a single public key and signature, Q and (R, s), to lock and unlock funds. This has two significant implications: on one hand, it means that Schnorr multisignatures are indistinguishable from regular Schnorr PaytoPublicKey transactions; on the other, and of significant importance with respect to Bitcoin’s scalability, it means that existing resourcestraining multisignature that contain multiple public keys and signatures can be replaced with significantly smaller, fixedsize Schnorr signatures — in other words: Schnorr reduces the size complexity of multisignature from O(m+n) to O(1).
Bitcoin uses elliptic curve cryptography, where public keys correspond to points on an elliptic curve, where each point is defined by a set of x– and ycoordinates. The elliptic curve used by Bitcoin, secp256k1, is defined in the Standards for Efficiency Cryptography (SEC), and uses 256bit (i.e. 32byte) numbers to represent the x– and ycoordinates of points on the curve.
ECDSA public keys
In Bitcoin, ECDSA public keys are encoded following SEC conventions. The format uses a prefix byte to indicate whether the uncompressed or compressed SEC format is used. In the uncompressed format, a public key’s 32byte x– and ycoordinates are encoded, leading to a total encoding size of 65 bytes when taking the onebyte prefix into account. In the compressed format, only the public key’s 32byte xcoordinates is encoded. (Note that the full public key can be reconstructed from this encoding: a public key’s ycoordinate can be derived from the key’s xcoordinate using the equation y²=x³+7 of Bitcoin’s elliptic curve secp256k1; the y² in the equation implies there exist two valid solutions for each xcoordinate; this ambiguity is resolved using information encoded in the SEC prefix.) ECDSA public keys encoded using the compressed SEC format thus have size of 33 bytes.
ECSSA public keys
According to BIP340, ECSSA public keys no longer use the SEC format. Instead, a custom encoding that uses no prefix byte is proposed, in which only the public key’s 32byte xcoordinate is encoded. Since the encoding lacks a prefix byte to resolve the issue of ambiguity concerning the ycoordinate, the ambiguity is resolved implicitly: for any given xcoordinate, exactly one of the two ycoordinate fulfilling the equation y²=x³+7 will be a quadratic residue (i.e., square number modulo the field size defined for Bitcoin’s elliptic curve secp256k1); by definition, a public key’s ycoordinate is always the quadratic residue. The size of the encoding of an ECSSA public key is, therefore, 32 bytes.
ECDSA signatures
ECDSA signatures consist of two 32byte numbers, r and s. In Bitcoin, such signatures are encoded according to the Distinguished Encoding Rules (DER), where each of the two numbers is prefixed by two bytes: one byte to encode the data type, which is an integer; another byte to indicate the length of the data. The encoding of the two numbers is then preceded by two more bytes: one to indicate that the signature consists of multiple elements (two to be exact, the encodings of r and s) and another to indicate the total length of the following encoding. This implies an overhead of six bytes for the encoding of two 32byte numbers, leading to a total ECDSA signature size of 70 bytes. Moreover, since Bitcoin supports multiple signature hash types (to indicate which parts of a message are signed), an additional byte is appended to the ECDSA signature to indicate the signature hash type. The total ECDSA signature size in Bitcoin according to this reasoning is thus 71 bytes. It is, however, worth noting that various effects can lead to the signature begin slightly smaller or larger. In practice, Bitcoin’s ECDSA signatures have an average size of 71.5 bytes (see Encoding of Signatures here).
ECSSA signatures
For ECSSA signatures, BIP340 proposes to discard the DER format is favor of a simpler, fixed encoding to avoid unnecessary overhead. In ECSSA, signatures comprise a point on the elliptic curve, R, and a 32byte number, s. In the signature, the encoding of the point R follows the previously discussed encoding for ECSSA public keys, so only its 32byte xcoordinate is encoded. The 32byte xcoordinate of R and the 32byte number s are encoded backtoback, resulting in a preliminary signature size of 64 bytes. Moreover, the signature hash type is omitted in the default case where the whole message is signed; an additional byte indicating the signature hash type is thus only used when a nondefault signature type is chosen, which, currently, is rarely the case. The total ECSSA signature size is thus only 64 bytes in the default case.
This section investigates the proposed P2TR lockingscript and witness formats and gives firstprinciplesbased size estimates for both.
Lockingscript format
The lockingscript format of P2TR outputs is OP_1 0x20 <pubkey>
, with OP_1
, the Bitcoin Script instruction used to indicate a new version 1 witness program corresponding to Schnorr/Taproot; 0x20
, the length of the following 32byte ECSSA public key in bytes (using hexadecimal representation); and <pubkey>
, the 32byte encoding an ECSSA public key.
Lockingscript size estimate
The encodings of the witness version and the length of the public key contribute one byte each; the public key contributes 32 bytes. The total lockingscript size is thus 34 bytes.
Witness format
As previously discussed, the P2TR locking scripts can be satisfied either using the key path (i.e., by providing a valid signature for the tweaked public key in the locking script) or the script path (i.e., by providing a valid input for the presented script, a script to be satisfied, an untweaked public key, and hashes of the leaves and branches of the Merkle tree required to calculate the tree’s root). In the following, the witness formats of both paths are discussed.
Keypath witness format
When using the key path, the witness format is <nitems> <len> <sig>
, with <nitems>
, the encoding of the number of witness items; <len>
, the length of the following Bitcoin ECSSA signature; and <sig>
, a Bitcoin ECSSA signature.
Keypath witness size estimate
The encoding of the length of the signature contributes one byte to the witness size. The signature is 64 bytes in case of the default signature hash type and 65 bytes in case of a custom signature hash type. Thus, the witness has a total size of either 65 or 66 bytes. Absent empirical data, the witnesssize estimate will be based on the assumption that the default signature hash type is used in most cases. The keypath witnesssize estimate based on this hypothesis is, therefore, 66 bytes.
Scriptpath witness format
When using the script path, the witness format is <nitems> <len> <input> <len> <script> <len> <c>
, with <nitems>
, the encoding of the number of witness items; <len>
, in each instance the length of the following item;<input>
, an input that fulfills the spending conditions set by the following script; <script>
, a script that will be interpreted as locking script; and <c>
, a control block: the first byte of the control block encodes the leaf version, which in case of the script path is always 0xc0 to indicate a scriptpath spend; the following 32 bytes of the control block is the encoding of the untweaked public key; finally, the control block holds 32byte blocks that encode the hashes of the leaves and branches of the Merkle tree that are necessary to reconstruct the Merkle root.
Scriptpath witness size estimate
The scripts in the witness can set arbitrary spending conditions and the data to fulfill these scripts varies significantly depending on these conditions. Moreover, depending on the number of disjoint spending conditions in the Merkle tree and the path to the script that is used for spending, the number of 32byte hashes in the control block can vary significantly. In light of this, giving an estimate for the size of scriptpath witnesses is pointless without empirical data.
The mathematical theory of Schnorr signature creation and validation was presented. Moreover, the theory behind tweaked Schnorr keys, and the application of such tweaked keys in Taproot to realize different spending paths (i.e., key and script paths) were covered. Further, an investigation of the benefits of Schnorr in the context of multisignatures revealed a size reduction from O(m+n), for previous mofn multisignature variants, to O(1), for mofn Schnorr multisignatures.
With a focus on the practical application of Schnorr signatures, the encodings of Schnorr public keys and signatures proposed for Bitcoin were investigated; the size requirements for Schnorr public keys and signatures were determined to be 32 and 64 bytes, respectively (compared to 33 and 71.5 bytes for ECDSA). Moreover, lockingscript and witness formats were discussed, for which, finally, size estimates were given: the lockingscript size is fixed at 34 bytes; the witness in case of the key path (i.e., for PaytoPublicKey and multisignature) was estimated to be 66 bytes; when it comes to the script path, a failure to establish meaningful estimates due to lack of empirical data had to be acknowledged.
If you found the information in this article useful, feel free to contribute: 16pGpaoAhzoneLdRdxPSo9xAAPhzWnP2dA
. If you have scientific, Bitcoinrelated freelance work, let me know.
Blockchain
Pawtocol CEO Karim Quazzani on New to the Street
Data is aggregated from IOT devices like our Blockchain Dog Tag, vets and more. Users maintain full control over the data about their pets
Pawtocol CEI(ETN) CEO Karim Quazzani dicusses the latest developments with Jane King on New to the Street
**
ABOUT US
Exploring the Block profiles Blockchain Technologies and Companies. Exploring the Block produces multipart series following the goals and achievements of the companies we follow and invite our audience to track the growth and challenges these companies face. Each series provides personal look at the company through the eyes of the CEO or company executive as they discuss their goals, roots and products with our experienced team of anchors/journalists to provide our viewing audience with who, what, where, when and why about the companies you want to learn about.
New To The Street profiles public companies, advertises and markets their products and services, and provides business news. New To The Street paves the way to the latest financial issues, offering a blend of business and financial services news reporting and indepth interviews relating to new products, economic analysis and public company profiles. New to the Street is produced by FMW Media Works Corp.
FMW Media
FMW Media Corp. operates one of the longestrunning U.S and International sponsored programming T.V. brands “NewToTheStreet,” and its blockchain show “Exploring The Block.” Since 2009, these brands run shows across major U.S. Television networks. These TV platforms reach over 540 million homes both in US and international markets. Developing 2additional shows “TheBestinNY” and “The Ultimate Listing0”
Originally posted at https://newtothestreet.com/pawtocolonnewtothestreet
Source: https://exploringtheblock.com/pawtocolceokarimquazzanionnewtothestreet/
Blockchain
Nebraska senator introduces bills to allow state banks to custody crypto
A Nebraska state senator has proposed new cryptofriendly legislation which could see his state become the next regulatory safe haven for FinTech firms.
Sworn in just two weeks ago, Republican Mike Flood today introduced the Transactions in Digital Assets Act and Adopt the Nebraska Financial Innovation Act to the state’s 107th Legislature.
The two bills lay out guidelines for state banks to be able to custody digital assets in addition to creating financial institutions dealing in digital assets for which Nebraska would provide “charter, operation, supervision, and regulation”. The measures would also give local courts the jurisdiction to hear claims “in both law and equity relating to digital assets.”
The proposed legislation will likely move to committee before a general file in the state legislature, where Republican lawmakers currently outnumber Democrats almost twotoone, 32 to 17.
The proposed bills also aim to address the problem of major banks in the United States discriminating against businesses and individual customers using crypto.
“The rapid innovation of blockchain and digital ledger technology, including the growing use of virtual currency and other digital assets, has resulted in many blockchain innovators and consumers being unable to access secure and reliable banking services, hampering development of blockchain services and products in the marketplace,” states the second bill.
“Many financial institutions in Nebraska and across the United States [refuse] to provide banking services to blockchain innovators and customers and also [refuse] to accept deposits in United States currency obtained from the sale of virtual currency or other digital assets.”
Flood, who previously served as a member and speaker of the Nebraska Legislature until 2013, said he planned to introduce bills intended to make his district a FinTech hub. In a meeting of the Norfolk Chamber of Commerce’s Governmental Affairs Committee last Wednesday, the state senator described cryptocurrency as a market with “great opportunity” for Nebraska.
“This is the future,” said Flood. “To be on the cutting edge of [crypto], I think, is good for us. We need to be a leader in FinTech. We in Norfolk have as much right to this new market as any other place in America.”
Under the 10th amendment to the U.S. Constitution, state laws can often be independent of, or even contradictory to federal laws. One example of this in the crypto space is exchanges such as Binance U.S. having to go state by state to legally make its services available to U.S. residents.
Last July, the Office of the Comptroller of the Currency announced that federally chartered banks would be allowed to provide custody services for cryptocurrency. Though the measures Flood proposed would not be needed for federally chartered banks in Nebraska, the proposals seemingly attempt to extend this benefit to statechartered banks.
Blockchain
Some institutional investors taking profit as Bitcoin retraces
A new report from crypto fund provider CoinShares has indicated that some institutional investors have been realizing profits during BTC’s recent consolidation.
CoinShares’ weekly digital asset flows report identifies $85 million in outflows from institutional crypto products this past week, asserting the data suggests “some investors are continuing to take profits after [BTC’s] strong price appreciation.”
The report noted the rising (tradeweighted) U.S. dollar, stating the USD index “is typically inversely correlated to Bitcoin prices,” and could explain why some investors are taking profits at the current levels.
The firm also identified modest outflows from Ethereumderived investment products, with $3 million leaving the markets.
Despite the profittaking, institutional inflows remain strong, with $359 million flooded into crypto investment products this week. Institutions still appear almost singlemindedly focused on BTC, with Bitcoin products representing all but 1% of the week’s total capital flows.
CoinShares notes that crypto inflows have returned to their preChristmas levels, following the 97% drop over three weeks seen after the holiday break. Daily volumes are currently up more than 450% yearoveryear.
Institutional products currently represent 6% of combined Bitcoin volume — down from 14% at the start of the month.
Much has been lately of the growing institutional appetites for crypto, with major global companies recently filling their treasuries with BTC.
After hosting more than 11 million BTC worth of futures trade in 2020, Chicago Mercantile Exchange announced last month that it plans to launch cashsettled Ethereum futures contracts in early February, pending regulatory approval.
On Jan. 20, Ninepoint Partners filed its final prospectus for a Bitcoin Trust conditionally approved by the Toronto Stock Exchange.

Blockchain1 week ago
Ethereum Whale Addresses With Over 10,000 ETH Continue to Grow In Numbers, Price Holds Above $1000

Blockchain5 days ago
Will exchanges run out of Ethereum?

Blockchain1 week ago
As Bitcoin Regains Lost Ground, Options Traders Bet on $52K Move By Late January

Blockchain1 week ago
‘Crypto is exactly like dot com bubble; Bitcoin, Ethereum can survive it’

Blockchain1 week ago
Ethereum Price Analysis: 12 January

Blockchain1 week ago
Shanghai Government Invests $5M in Blockchain Startup Conflux

Blockchain1 week ago
Coinbase Custody Lists DeFi Project BarnBridge

Blockchain1 week ago
Brian Brooks, CryptoFriendly OCC Leader, Steps Down