38
I'll try answering this again in a different way,
using small numbers to keep it readable.
convert the private key to binary representation, so decimal number 105, which is 0x69 in hex, becomes 01101001.
calculate this list of points, by repeatedly doubling the Generator point G:
1*G
2*G = G+G
4*G = 2*G + 2*G
8*G = 4*G + 4*G
16*G = 8*G + 8*G
32*G = 16*G + ...
36
Warning: I've never actually worked with the Schnorr signature scheme. The
following is my analysis based on reading the Wikipedia
article, the ed25519
page, and some discussions between devs in
#bitcoin-dev.
Likely Changes
Changed op code behavior: we will need an op code to check
Schnorr signatures. With a hard fork, we can redefine
op_checksig and
...
18
Your question seems to assume that the only goal is minimizing on-chain transaction size. Reducing size and related costs is certainly something that can be improved upon, but it's far from the only thing. The primary advantages of the Schnorr proposal are:
Better privacy, by making different multisig spending policies indistinguishable on chain. When ...
15
Yes, one validation per block, but not one signature per block.
To clear up confusion, there are 3 distinct technologies involved here:
(1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified ...
15
They will be distinguishable, but they will still be bech32 addresses.
The introduction of Schnorr signatures requires a new type of output. Segwit was designed with such extensibility in mind, and it defines 17 version numbers. Currently, only version 0 is used. Segwit v0 outputs with a 20-byte hash are known as P2WPKH outputs, and v0 outputs with a 32-...
13
No, ECDSA and EC-Schnorr, as well as related schemes like EdDSA, all belong to the class of elliptic curve cryptography. Their security is based on the assumption that the EC discrete logarithm is unfeasibly hard to compute. This assumption is not true if a sufficiently strong general purpose quantum computer would exist.
Quantum resistant signature ...
13
MuSig is interactive because each signer needs to provide a signature nonce (effectively randomness) before signing. This is not specific to MuSig, but applies to any discrete logarithm-based multisignature scheme as far as I know.
Now to understand why multiple communication rounds are necessary let's look at what happens at each of them, starting from the ...
12
You're right that the elliptic curve multiplication is indeed the most expensive operation in the validation algorithm. And as both single signature validation and batch validation require two EC multiplication per signature, it would seem that no speedup can be gained from batching.
However, several algorithms are known for computing the sum of multiple EC ...
11
The Schnorr implementation was never in Bitcoin Core. Rather it is in the libsecp256k1 library that is a subtree in Bitcoin Core. The commit you reference is actually a commit in that library which appears in Core's commit history because the subtree in Core is periodically updated with the libsecp256k1 upstream source code.
The reason for removal is ...
11
From the (very recently updated) bip-schnorr draft:
Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is a quadratic residue by negating the point if ...
11
Schnorr signatures will not replace ECDSA. Schnorr signature verification is expected to be implemented with the Taproot soft-fork using SegWit witness version 1. This means only outputs that are locked in v1 SegWit version are expected to produce a valid Schnorr signatures.
ECDSA will continue to be used for spending current non-SegWit and v0 SegWit ...
10
Schnorr will replace ECDSA, the signing algorithm, but both still use the same elliptic curve and thus the same public and private keys, etc.
Regardless, compatibility with ECDSA must be kept too even if Schnorr is used, because otherwise all old nodes would see the schnorr signatures as invalid signatures, and all old transactions would be seen as invalid ...
10
I'm not sure what simplified variant you're referring to, but this is a great question.
There are a number of reasons.
First, RFC6979 is not cheap and fairly complex. Computing a single candidate nonce costs 22 invocations of the SHA256 compression function. Hashes are fast, but this actually corresponds to hashing 1400 bytes which isn't trivial anymore ...
9
Why was ECDSA chosen over Schnorr Signatures in the inital design?
You'll need to ask Satoshi to know for sure, but my guess is simply because ECDSA was well standardized at the time, while no Elliptic Curve Schnorr based schemes were.
One of the reasons why an ECDSA standard existed but no EC-Schnorr ones may be patents. DSA was designed as a variant of ...
9
Yes you can do public key recovery with EC Schnorr. Consider
R = kG, [r = R.x, s = k + H(r, m)d], Q = dG
verify:
sG = ?R + H(r, m)Q
recovery:
sG = kG + H(r, m) dG = R + H(r, m)Q
so
Q = 1 / H(r, m) * (sG - R).
(And to compute R from r if R is point-compressed, R = (r,f(r)) R' = (r,-f(r)) and try both R and R' by checking if the signature is valid with ...
8
One of the most common use of script in Bitcoin is to construct logically atomic operations, such as "Tx2 happens if and only if Tx1 happens".
Scriptless scripts tells us how to use the additive properties of schnorr-signatures to construct atomic transactions without using script. Doing so this way will make them more efficient and private.
Taproot is an ...
7
A P2WPKH PubKey is shorter than a P2WSH PubKey.
No, not quite. A P2WPKH address is shorter than a P2WSH address. The addresses are both based on a hash of the underlying witness program (i.e. the locking conditions of the output). In the case of Pay to Witness Public Key Hash (P2WPKH) the witness program contains only the public key. On the other hand, Pay ...
6
When you sign a transaction with schnorr-signatures, it does not include the pubkey in the transaction data.
What? Schnorr signature validation still need public keys.
1)Does this mean the input addresses become unknown, aka creating a opaque blockchain ?
No, there are still addresses just like before (or more technically: every input still explicitly ...
6
SegWit blocks aren't limited in bytes anymore but rather in weight. The maximum weight for a block is 4M. The weight of non-witness data is 4x its number of bytes.
So, yes, decreasing the amount of signature-data frees up some weight which can then be filled by more transactions. Yet those new transactions also contain some non-witness data which is more ...
6
Scriptless scripts are more like the constructs used in HTLCs and Taproot is more like P2SH.
The common example used for scriptless scripts is adaptor signatures. With adaptor signatures, what one person A wants is a valid signature which person B is able to provide but only if they receive payment. This scriptless script allows person A to give person B ...
6
Here's a self-contained Python script that does the conversion. You can check its work by comparing to entering your private key as the "Secret Exponent" at Brainwallet. I took the script from this Bitcointalk thread and stripped out unnecessary stuff (like the code to use the public key to sign a message and verify that signature).
Converting the Python to ...
6
Nonces must not be reused! In particular, in MuSig, nonces can not be reused
for other combinations of public keys or messages (also if everyone uses the
same public nonces all the time). This would leak private keys.
You pre-share fresh nonces by running multiple signing rounds in parallel.
With the library you link to
(secp256k1-zkp) this is
secure as you ...
5
To perform an atomic swap, both assets need to be locked up to ensure the eponymous atomic execution of both payments or neither. Traditionally, this uses a complex output script that has two outcomes. On both chains, funds are locked such that either the receiving party signs with their private key while also revealing a preimage, or the original owner can ...
5
I think it's important to note first that BIP341-BIP342 are improvements to the Bitcoin script "framework" more than they are improvements to the smart contracting "functionality".
All Bitcoin scripts can do in practice is enforce combinations of conditions on signatures by certain (sub)sets of signers, timelocks, and revealing hashes. At ...
5
SegWit introduced versioned witness programs. When satisfying a script to spend coins you need to provide a redeem script consisting of a version byte and a witness program. The version introduced with SegWit was version 0 (zero).
The Taproot proposal uses this SegWit versioning system by introducing spending rules for version 1. The witness program to ...
5
To add to Michael Folkson's answer, a question one may have is what the differences are between witness versions and leaf versions. Why do we need both?
Leaf versions are not revealed until an output is spent, and thus is not known in general to the payer (who is only given an address). For native witness outputs, the witness version is visible from the the ...
4
The construction you're suggesting will likely work as long as you don't sign more than one message. By effectively choosing the R points ahead of time, you've constructed a single-show signature.
However, the derivation you're using for the different R values is pointless. It's not enough that you don't reuse R values; you can't use multiple related R ...
4
Speedup in well optimized cryptographic functions are hard to come by. In libsecp256k1 we'll usually celebrate a 4% algorithmic speedup. Figures on the order of 2x are reasonable for the usage in Bitcoin, though larger might be possible in the future during initial block download since much larger batches could be used.
A single validation on a single core ...
4
A schnorr signature, without key prefixing, is a tuple {pubkey (P), message (m), R, s} where the equation R == sG + H(R||m)P holds.
Now, assume you have pubkeys P and P2 who's discrete logs differ by c which is known to me, as is the case for non-hardened BIP 32 when I know the extended pubkey (P2 == P + cG). If I know a signature by pubkey P of message m, ...
4
It's easy to verify the order (n): Multiply G by n and find that you get the point at infinity. This proves that n is either the order or a multiple of it. Then convince yourself n is prime using a Baillie-PSW primality test, so it must be the order itself and not a multiple of it.
Finding the order is not quite so simple as verifying it. To do so you ...
Only top voted, non community-wiki answers of a minimum length are eligible
