In a recent article, script and witness sizes for all transaction output types existing as of May 2020 were investigated. This article is a follow-up that addresses the not yet implemented but highly anticipated Pay-to-Taproot (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 multi-signatures 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 locking-script and witness sizes is limited to a first-principle analysis since empirical data for validation is not yet available.
Formally defined as SegWit version 1 output type in BIP341, the proposed Pay-to-Taproot (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 high-level introduction to the Schnorr signature algorithm. Then, the use of Schnorr in Taproot and proposed Schnorr multi-signatures are discussed. Next, the encoding of Schnorr public keys and signatures in Bitcoin is addressed. Finally, Taproot’s locking-script 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 multi-signatures in the following sections.
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 32-byte 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 32-byte value, s, is calculated as
s=k+H(R‖P‖m)p, with k, the previously determined random 32-byte 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).
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 becomes
k+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 Pay-to-Public-Key and Pay-to-Script-Hash 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.
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.
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, yields
k+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.
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 becomes
Moreover, substituting q for p+t with tweak t=H(P,S), yields
Next, the terms in parenthesis on the left side of the equation are multiplied with G, so the equation becomes
Finally, P is substituted for pG on the left, which yields
P+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 script-path 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 multi-signatures are discussed.
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.
The additivity property allows for the creation of a Schnorr multi-signature scheme in which a single public key can be used to realize a multi-signature requirement. Moreover, a single signature is sufficient to unlock the funds.
A Schnorr multi-signature public key, Q, is constructed from multiple individual public keys, Qᵢ: in essence, Q=Q₁+…+Qₙ. A valid Schnorr multi-signature, (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, m-of-n Schnorr multi-signatures 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 multi-signatures are indistinguishable from regular Schnorr Pay-to-Public-Key transactions; on the other, and of significant importance with respect to Bitcoin’s scalability, it means that existing resource-straining multi-signature that contain multiple public keys and signatures can be replaced with significantly smaller, fixed-size Schnorr signatures — in other words: Schnorr reduces the size complexity of multi-signature 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 y-coordinates. The elliptic curve used by Bitcoin, secp256k1, is defined in the Standards for Efficiency Cryptography (SEC), and uses 256-bit (i.e. 32-byte) numbers to represent the x– and y-coordinates 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 32-byte x– and y-coordinates are encoded, leading to a total encoding size of 65 bytes when taking the one-byte prefix into account. In the compressed format, only the public key’s 32-byte x-coordinates is encoded. (Note that the full public key can be reconstructed from this encoding: a public key’s y-coordinate can be derived from the key’s x-coordinate 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 x-coordinate; 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 32-byte x-coordinate is encoded. Since the encoding lacks a prefix byte to resolve the issue of ambiguity concerning the y-coordinate, the ambiguity is resolved implicitly: for any given x-coordinate, exactly one of the two y-coordinate 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 y-coordinate is always the quadratic residue. The size of the encoding of an ECSSA public key is, therefore, 32 bytes.
ECDSA signatures consist of two 32-byte 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 32-byte 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).
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 32-byte number, s. In the signature, the encoding of the point R follows the previously discussed encoding for ECSSA public keys, so only its 32-byte x-coordinate is encoded. The 32-byte x-coordinate of R and the 32-byte number s are encoded back-to-back, 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 non-default 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 locking-script and witness formats and gives first-principles-based size estimates for both.
The locking-script 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 32-byte ECSSA public key in bytes (using hexadecimal representation); and
<pubkey>, the 32-byte encoding an ECSSA public key.
Locking-script 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 locking-script size is thus 34 bytes.
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.
Key-path 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.
Key-path 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 witness-size estimate will be based on the assumption that the default signature hash type is used in most cases. The key-path witness-size estimate based on this hypothesis is, therefore, 66 bytes.
Script-path 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 script-path spend; the following 32 bytes of the control block is the encoding of the untweaked public key; finally, the control block holds 32-byte blocks that encode the hashes of the leaves and branches of the Merkle tree that are necessary to reconstruct the Merkle root.
Script-path 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 32-byte hashes in the control block can vary significantly. In light of this, giving an estimate for the size of script-path 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 multi-signatures revealed a size reduction from O(m+n), for previous m-of-n multi-signature variants, to O(1), for m-of-n Schnorr multi-signatures.
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, locking-script and witness formats were discussed, for which, finally, size estimates were given: the locking-script size is fixed at 34 bytes; the witness in case of the key path (i.e., for Pay-to-Public-Key and multi-signature) 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, Bitcoin-related freelance work, let me know.
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
Exploring the Block profiles Blockchain Technologies and Companies. Exploring the Block produces multi-part 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 in-depth interviews relating to new products, economic analysis and public company profiles. New to the Street is produced by FMW Media Works Corp.
FMW Media Corp. operates one of the longest-running 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 2-additional shows “TheBestinNY” and “The Ultimate Listing0”
Originally posted at https://newtothestreet.com/pawtocol-on-new-to-the-street
Nebraska senator introduces bills to allow state banks to custody crypto
A Nebraska state senator has proposed new crypto-friendly 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 two-to-one, 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 state-chartered banks.
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 (trade-weighted) 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 Ethereum-derived investment products, with $3 million leaving the markets.
Despite the profit-taking, institutional inflows remain strong, with $359 million flooded into crypto investment products this week. Institutions still appear almost single-mindedly 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 pre-Christmas levels, following the 97% drop over three weeks seen after the holiday break. Daily volumes are currently up more than 450% year-over-year.
Institutional products currently represent 6% of combined Bitcoin volume — down from 14% at the start of the month.
After hosting more than 11 million BTC worth of futures trade in 2020, Chicago Mercantile Exchange announced last month that it plans to launch cash-settled 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.
Will exchanges run out of Ethereum?
Bitcoin Cash, Zcash, Decred Price Analysis: 17 January
Charted: Chainlink (LINK) Remains In Strong Uptrend, Why It Could Test $25
Decred co-founder explains the possible effects of a CBDC takeover
Cardano “Working On Something” That Could Solve Twitter’s Decentralization Dilemma
Ethereum, Monero, Algorand Price Analysis: 17 January
Healthcare Jobs of the Future
Will Bitcoin see another trend reversal in 2021?
Michael Novogratz’s Galaxy Digital to Jump Into BTC Mining
Analyst: Hodlers will be this year’s biggest Bitcoin gainers
Top 5 cryptocurrencies to watch this week: BTC, LINK, UNI, XTZ, ATOM
Over 31% of People in Latin America Want to Invest in Bitcoin
China-based BSN Readies International CBDC Platform
Biden Appointed SEC Chair Gary Gensler is not Going to Save Ripple’s XRP Token
ShapeShift working on a cross-chain DEX, reveals CEO Voorhees
After alleged hack, Russian crypto exchange Livecoin shuts down
Tether’s General Counsel: iFinex v. NYAG Case Continues with a Court Meeting in 30 Days
EOS, BAT, Dogecoin Price Analysis: 16 January
Crypto exchange Bitpanda opens pre-orders for Visa debit card
Binance Coin, STEEM, Compound Price Analysis: 16 January
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, Crypto-Friendly OCC Leader, Steps Down