[bitcoin-dev] OP_CHECKWILDCARDSIGVERIFY or "Wildcard Inputs" or "Coalescing Transactions"

Discussion:

Chris Priest via bitcoin-dev

2015-11-24 17:34:35 UTC

Here is the problem I'm trying to solve with this idea:

Lets say you create an address, publish the address on your blog, and
tell all your readers to donate $0.05 to that address if they like
your blog. Lets assume you receive 10,000 donations this way. This all
adds up to $500. The problem is that because of the way the bitcoin
payment protocol works, a large chunk of that money will go to fees.
If one person sent you a single donation of $500, you would be able to
spend most of the $500, but since you got this coin by many smaller
UTXO's, your wallet has to use a higher tx fee when spending this
coin.

The technical reason for this is that you have to explicitly list each
UTXO individually when making bitcoin transactions. There is no way to
say "all the utxos". This post describes a way to achieve this. I'm
not yet a bitcoin master, so there are parts of this proposal that I
have not yet figured out entirely, but I'm sure other people who know
more could help out.

**OP_CHECKWILDCARDSIGVERIFY**

First, I propose a new opcode. This opcode works exactly the same as
OP_CHECKSIGVERIFY, except it only evaluates true if the signature is a
"wildcard signature". What is a wildcard signature you ask? This is
the part that I have not yet 100% figured out yet. It is basically a
signature that was created in such a way that expresses the private
key owners intent to make this input a *wildcard input*

** wildcard inputs **

A wildcard input is defined as a input to a transaction that has been
signed with OP_CHECKWILDCARDSIGVERIFY. The difference between a
wildcard input and a regular input is that the regular input respects
the "value" or "amount" field, while the wildcard input ignores that
value, and instead uses the value of *all inputs* with a matching
locking script.

** coalescing transaction"

A bitcoin transaction that

Gavin Andresen via bitcoin-dev

2015-11-24 20:32:37 UTC

Permalink

On Tue, Nov 24, 2015 at 12:34 PM, Chris Priest via bitcoin-dev <

Post by Chris Priest via bitcoin-dev
The technical reason for this is that you have to explicitly list each
UTXO individually when making bitcoin transactions. There is no way to
say "all the utxos". This post describes a way to achieve this. I'm
not yet a bitcoin master, so there are parts of this proposal that I
have not yet figured out entirely, but I'm sure other people who know
more could help out.

So every input has:
32-byte hash (transaction being spent)
4-byte output (output being spent)
4-byte sequence number
... plus the scriptSig. Which is as small as about 73 bytes if you're
spending a raw OP_CHECKSIG (which you can't do as a bitcoin address, but
could via the BIP70 payment protocol), and which is at least two serialized
bytes.

Best case for any scheme to coalesce scriptSigs would to somehow make
all-but-the-first scriptSig zero-length, so the inputs would be 42 bytes
instead of 40+73 bytes -- the coalesce transaction would be about one-third
the size, so instead of paying (say) $1 in transaction fees you'd pay 37
cents.

That's in the gray are of the "worth doing" threshold-- if it was a 10x
improvement (pay 10 cents instead of $1) it'd be in my personal "definitely
worth the trouble of doing" category.

RE: the scheme: an OP_RINGSIGVERIFY is probably the right way to do this:
https://en.wikipedia.org/wiki/Ring_signature

The funding transactions would be: <public key> OP_RINGSIGVERIFY
... which might could be redeemed with <ring signature> for one input and
then... uhh... maybe just <index_to_input_with_signature> for the other
inputs that are part of the same ring signature group (OP_0 if the first
input has the signature that is good for all the other public keys, which
would be the common case).

--
--
Gavin Andresen

Chris Priest via bitcoin-dev

2015-11-24 21:01:26 UTC

Permalink

A coalescing transaction in my scheme is the same size as a normal
transaction. You only include one UTXO, the rest are implied based on
the presence of the OP_CHECKWILDCARDSIGVERIFY opcode.

The code that determines if a UTXO is spent or not will need to be
modified to include a check to see if any matching coalescing
transactions exist in any later block. Maybe there should be a
"coalescing pool" containing all coalescing transactions that make
such a check faster.

The part I'm not too sure about is the "wildcard signature". I'm not
too versed in cryptography to know how exactly to pull this off, but I
think it should be simple.
You'd just have to some way inject a flag into the signing process
that can be verified later.

I originally wanted the "wildcardness" of the transaction expressed by
the transaction version number.
Basically any input that exists within a "version 2 transaction" is
viewed as a wildcard input. Then I realized whats to stop someone from
modifying the transaction from version 1 to version 2 and stealing
someones funds. The "wildcardness" must be expressed in the signature
so you know that the private key holder intended all inputs to be
included. Hence the need for a new opcode.

btw, this scheme is definitely in the 10x or higher gain. You could
potentially spend an unlimited number of UTXOs this way.

Post by Gavin Andresen via bitcoin-dev
On Tue, Nov 24, 2015 at 12:34 PM, Chris Priest via bitcoin-dev <

32-byte hash (transaction being spent)
4-byte output (output being spent)
4-byte sequence number
... plus the scriptSig. Which is as small as about 73 bytes if you're
spending a raw OP_CHECKSIG (which you can't do as a bitcoin address, but
could via the BIP70 payment protocol), and which is at least two serialized
bytes.
Best case for any scheme to coalesce scriptSigs would to somehow make
all-but-the-first scriptSig zero-length, so the inputs would be 42 bytes
instead of 40+73 bytes -- the coalesce transaction would be about one-third
the size, so instead of paying (say) $1 in transaction fees you'd pay 37
cents.
That's in the gray are of the "worth doing" threshold-- if it was a 10x
improvement (pay 10 cents instead of $1) it'd be in my personal "definitely
worth the trouble of doing" category.
https://en.wikipedia.org/wiki/Ring_signature
The funding transactions would be: <public key> OP_RINGSIGVERIFY
... which might could be redeemed with <ring signature> for one input and
then... uhh... maybe just <index_to_input_with_signature> for the other
inputs that are part of the same ring signature group (OP_0 if the first
input has the signature that is good for all the other public keys, which
would be the common case).
--
--
Gavin Andresen

Bryan Bishop via bitcoin-dev

2015-11-24 21:51:12 UTC

Permalink

On Tue, Nov 24, 2015 at 11:34 AM, Chris Priest via bitcoin-dev <

Post by Chris Priest via bitcoin-dev
**OP_CHECKWILDCARDSIGVERIFY**

Some (minor) discussion of this idea in -wizards earlier today starting
near near "09:50" (apologies for having no anchor links):
http://gnusha.org/bitcoin-wizards/2015-11-24.log

- Bryan
http://heybryan.org/
1 512 203 0507

Dave Scotese via bitcoin-dev

2015-11-24 23:28:33 UTC

Permalink

What is required to spend bitcoin is that input be provided to the UTXO
script that causes it to return true. What Chris is proposing breaks the
programmatic nature of the requirement, replacing it with a requirement
that the secret be known. Granted, the secret is the only requirement in
most cases, but there is no built-in assumption that the script always
requires only that secret.

This idea could be applied by having the wildcard signature apply to all
UTXOs that are of a standard form and paid to a particular address, and be
a signature of some kind of message to that effect. I imagine the cost of
re-scanning the UTXO set to find them all would justify a special extra
mining fee for any transaction that used this opcode.

Please be blunt about any of my own misunderstandings that this email makes
clear.

On Tue, Nov 24, 2015 at 1:51 PM, Bryan Bishop via bitcoin-dev <

Post by Bryan Bishop via bitcoin-dev
On Tue, Nov 24, 2015 at 11:34 AM, Chris Priest via bitcoin-dev <

Post by Chris Priest via bitcoin-dev
**OP_CHECKWILDCARDSIGVERIFY**

Some (minor) discussion of this idea in -wizards earlier today starting
http://gnusha.org/bitcoin-wizards/2015-11-24.log
- Bryan
http://heybryan.org/
1 512 203 0507
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

--
I like to provide some work at no charge to prove my value. Do you need a
techie?
I own Litmocracy <http://www.litmocracy.com> and Meme Racing
<http://www.memeracing.net> (in alpha).
I'm the webmaster for The Voluntaryist <http://www.voluntaryist.com> which
now accepts Bitcoin.
I also code for The Dollar Vigilante <http://dollarvigilante.com/>.
"He ought to find it more profitable to play by the rules" - Satoshi
Nakamoto

Chris Priest via bitcoin-dev

2015-11-24 23:48:16 UTC

Permalink

Post by Dave Scotese via bitcoin-dev
This idea could be applied by having the wildcard signature apply to all
UTXOs that are of a standard form and paid to a particular address, and be
a signature of some kind of message to that effect.

I think this is true. Not *all* transactions will be able to match the
wildcard. For instance if someone sent some crazy smart contract tx to
your address, the script associated with that tx will be such that it
will not apply to the wildcard. Most "vanilla" utxos that I've seen
have the formula: OP_DUP OP_HASH160 [a hash corresponding to your
address] OP_EQUALVERIFY OP_CHECKSIG". Just UTXOs in that form could
apply to the wildcard.

On 11/24/15, Dave Scotese via bitcoin-dev

Post by Dave Scotese via bitcoin-dev
What is required to spend bitcoin is that input be provided to the UTXO
script that causes it to return true. What Chris is proposing breaks the
programmatic nature of the requirement, replacing it with a requirement
that the secret be known. Granted, the secret is the only requirement in
most cases, but there is no built-in assumption that the script always
requires only that secret.
This idea could be applied by having the wildcard signature apply to all
UTXOs that are of a standard form and paid to a particular address, and be
a signature of some kind of message to that effect. I imagine the cost of
re-scanning the UTXO set to find them all would justify a special extra
mining fee for any transaction that used this opcode.
Please be blunt about any of my own misunderstandings that this email makes
clear.
On Tue, Nov 24, 2015 at 1:51 PM, Bryan Bishop via bitcoin-dev <

Post by Bryan Bishop via bitcoin-dev
On Tue, Nov 24, 2015 at 11:34 AM, Chris Priest via bitcoin-dev <

Post by Chris Priest via bitcoin-dev
**OP_CHECKWILDCARDSIGVERIFY**

Jannes Faber via bitcoin-dev

2015-11-25 00:38:02 UTC

Permalink

Few issues I can think of:

1. In its basic form this encourages address reuse. Unless the wildcard can
be constructed such that it can match a whole branch of an HD wallet.
Although I guess that would tie all those addresses together making HD moot
to begin with.

2. Sounds pretty dangerous during reorgs. Maybe such a transaction should
include a block height which indicates the maximum block that any utxo can
match. With the requirement that the specified block height is at least 100
blocks in the past. Maybe add a minimum block height as well to prevent
unnecessary scanning (with the requirement that at least one utxo must be
in that minimum block).

3. Seems like a nice way to the reduce utxo set. But hard to say how
effective it would really be.
On 25 Nov 2015 12:48 a.m., "Chris Priest via bitcoin-dev" <