Bitcoin Forum

This is obsolete. See my new proposal below: https://bitcointalk.org/index.php?topic=153401.msg11329252#msg11329252

We should encourage "good transactions", which are: 1. small in size, 2. with less outputs, 3. with practically spendable outputs

Targets 2, 3 are important for maintaining a reasonable size of UTXO set.

The current block size restriction, however, considers only the target 1. Miners will accept polluting transactions (with lots of practically unspendable outputs) as long as enough fee is paid. However, every full nodes has to maintain the inflated UTXO set.

If the block size limit is to be increased, it could be determined by more factors, not just the absolute size.

I have a rough idea:

Let's denote:

S₀, S₁,.....,S_n: Amount of Satoshis of the output 0, 1 ..... n.
Size: size of the transaction in kB.

The adjusted transaction size is defined as:

Size * (1/(log₂S₀+1)+1/(log₂S₁+1)+..+1/(log₂S_n+1))

The value of 1/(log₂S_n+1) increases exponentially as the output size decreases. The value is 1 for 1 satoshi, 0.5 for 2 satoshi, 0.13 for 1 uBTC, 0.057 for 1mBTC, and 0.036 for 1 BTC.  

The adjusted block size is defined as the sum of adjusted transaction size.

If the real block size is < 1MB, the adjusted block size is not consider. If the real block size is > 1MB, the adjusted block size must be smaller than a certain constant.

Many problems are solved with a system like this:

1. Block size is still scare. If it is < 1MB, it is equivalent to current limit. If it is > 1MB, "good transactions" are prioritised
2. Miners will have an incentive to exclude dust outputs, because that will increase the adjusted block size
3. Miners will love transactions with less outputs, so the UTXO set could be reduced.
4. People trying to send dust outputs and/or inflate UTXO set have to pay more miner fee to compensate for their pollution
5. The block size, which costs bandwidth and disk space, is still accounted.

Since there must be a hard fork when lifting the max block size, adding extra rules like these won't make the change more complicated.

Start a mining pool. You can implement any rule you want with regards to which transactions get included and which do not. Convince other miners that your rules are the best and they will vote with their hashing power.

No, this is a hard fork.

Granted that your block still needs to be valid for the rest of the network to accept it.

But your goal of "encouraging good transactions" does not require any changes to the protocol. You can reject any non-good transactions in your pool and just ask other miners to support you by mining in your pool.

Isn't that a much better solution than putting mandatory fee selection rules in the protocol?

Oh come now, surely it is obvious that other people not being forced to obey "the" rules is doubleplus-ungood?

-MarkM-

This is actually a response to the other thread: https://bitcointalk.org/index.php?topic=153133.0

Using this proposal, we can increase the max block size without bloating the UTXO set

This.

The argument that a block size limit is necessary to prevent excessive centralization applies equally well to a limit on the per block expansion of the utxo set.  So I think this justifies the creation of such a limit, if a block size limit is to be maintained.

Also, I don't see why we would need to have a single metric to describe usage of the two scarce resources, block space and utxo set space.  Wouldn't it be simpler to just have separate limits for both?  They consume distinct physical resources - bandwidth and storage, respectively - and so these parameters should be somewhat orthogonal.

Agreed.

We may have a UTXO index, which is the total number of outputs in a block minus the total number of inputs in a block, and have a hard limit for it

There was a thread on bitcoin-development about this too...

http://sourceforge.net/mailarchive/forum.php?thread_name=CABOyFfrPTYeq-g5tgte2HWfvBiBcRLw_Bvyk_X2hXMWVoW3dgQ%40mail.gmail.com&forum_name=bitcoin-development

Apologies for necro-ing this thread, but the OP does seem particularly relevant to Gavin's concerns about UTXO bloat: http://gavinandresen.ninja/utxo-uhoh

and Gregory's recent post:
http://sourceforge.net/p/bitcoin/mailman/message/34097489/

Aligning the demand for larger blocks with pressure to maintain a cleaner UTXO set, may be more constructive, beneficial long-term, and a more immediate priority than concerns about further pressure for the fees market.

Yea, this has been in several different threads before (I'm not even sure if I was aware of this one). It seems obvious and correct to account for UTXO impact; though the exact parameters seem less clear (though almost any would be workable; though I'd rather not go implement a separate fixed point log for this.)

It also hasn't gone anywhere though these things are trivial to implement; because basically they're more or less tolerable to go without them at the current limits (though they'd be nice; utxo is still growing at a somewhat alarming rate; and the dust limits are kinda ugly hacks); and most of the push for larger blocks starts with the premise that there isn't major risk or trade-off worth addressing, and by that metric additional complexity doesn't sound justified-- and indeed, almost anything is more complex than "change a 1 to a 20". :)

I don't like the framing "Miners will have an incentive to exclude dust" ... rather, transactions have a cost, the change makes the economic cost better aligned with the true costs, and the change means transactions will have to pay in proportion to their costs-- in my suggestion it's set so that creating outputs effectively prepays much of the cost of spending them;  but there is no discrimination against "dust", miners make no judgement-- there is a cost and it's up to the users to justify it. :)

I don't like having txout values in the terms because that has an implicit scaling factor between the value of coins and the value of bytes, and because the value is actually unrelated to the costs to the network. My formula works with bytes all around, though there is some scaling because signatures tend to be much bigger than outputs and limits because I'm trying to avoid some edge cases like miners bloating the utxo set with cheaply spendable outputs in order to store-and-forward their blocksize.

I wrote this long time ago when I knew Bitcoin not very well. But I always think this has to be done if we increase the max block size.

I would like to rewrite it as follow:

We will formally define "utxoSize", which is

txid (32 bytes) + txoIndex (varInt) + scriptPubKey length (varInt) + scriptPubKey (? bytes) + value (8 byte) + coinbase (1 byte) + coinbase block height (0 or 4 bytes)

txid is the txid of the utxo
txoIndex is the index of the utxo in the tx, recorded as varInt
scriptPubKey length is the length of the scriptPubKey of the utxo, a varInt
scriptPubKey is the scriptPubKey of the utxo
value is the utxo value in Satoshis
coinbase is an indicator to show whether the utxo is a coinbase reward
if it is a coinbase reward, 4 more bytes is needed to record the block height

I think these are the minimal amount of data needed to store utxo. the utxo set needs to show whether an utxo is from coinbase due to the 100-block rule.

However, if the utxo contains ANY one of the invalid OP_CODE, e.g. OP_RETURN, OP_VERIF, OP_CAT which guarantees the script to fail, the utxoSize is set to zero.

For each block, we need to calculate the net change in UTXO size, which is


With utxoDiff, we may have a soft-fork rule of one of the followings:

• 1. Put a hardcoded cap to utxoDiff for each block. Therefore, we will be sure that the UTXO set won't grow too fast; or
• 2. If a block has a small (or even negative) utxoDiff, a higher MAX_BLOCK_SIZE is allowed

That will encourage miners to accept txs with small or negative utxoDiff, which will keep the UTXO set small.

An UTXO only really needs to contain a hash of the output point (and height).  The spending transaction should include all the information required, when spending.

That saves storing the information in RAM, i.e. the owner of the transaction stores the info.

It wouldn't even be required to store the entire hash.  A node could salt the hashes and collisions would be very unlikely.

The database would be a map of

Hash(key_salt | txid | n) maps to Hash(value_salt | OutPoint | height | ... )

If each hash was reduced to the lower 8 bytes and there were 10 million in the UTXO set, the odds of a collision is still tiny (around 1 in 180,000).

To falsely spend an UTXO, an attacker would need 2 ^ 63 attempts, but that requires knowning the target node's value_salt.

Using that system, the entire UTXO set would be 16 bytes per entry for the key and value.

How about the scriptPubKey and value of the utxo? These are not part of the spending tx.

I meant that the info isn't strictly needed in the UTXO database (in general).  An extended transaction format could include the scriptPubKey and the value (and also the height, for coinbase spends).

This moves the cost of storing that info from RAM in every node to whoever wants to spend the transaction.  P2SH outputs already effectively do this (well not the value), but there is no reason that all transactions couldn't support it.  

During the transitiion, tx messages could be converted into etx messages by full nodes.  Eventually, tx messages could be depreciated.  Wallet software would have to manage the info for any coins held in its wallet.

ok, but I don't understand the meaning of your: Hash(key_salt | txid | n) maps to Hash(value_salt | OutPoint | height | ... )

Why don't just use an index of Hash(salt|txid|n|height|scriptPubKey|value)? The etx message will provide all these information (expect the salt which is a secret of the node).

Also, the etx message won't need to provide scriptPubKey if it is a standard one like P2PK, P2PKH or P2SH. Just use a byte to indicate the type is enough.

I was thinking you need to be able to look it up from the database, so need (txid | n) to be a key.  However, you are right a hash set is sufficient, if the etx has all the required additional info.

This drops things to 8 bytes per UTXO output for serialization and slightly more due to hashset overhead for RAM.

There could be an eblock too.  This allows nearly complete block verification without needing any info outside the eblock.  The only check is that the UTXOs all actually exist.

I think this would help with the consensus library.  You pass it an eblock message and it returns a list of UTXOs that must exist for the block to be valid and also a list of new UTXO hashes.

This means that (almost) all the complexity of block verification (script and crypt) is handled internally in the library.  The only thing that the outside client needs to be is manage the UTXO digests.

It might be better to use hash(salt | hash(<info>)), so that the salting can be done outside the consensus library.  The consensus library would use 32 byte digests.


It still needs to provide the info to generate the scriptPubKey (address or serialized scriptPubKey).

You don't need any extra info for P2PKH or P2SH because you can reconstruct the scriptPubKey with scriptSig.

(For P2PK and BIP11 multi-sig, however, the etx has to provide the scriptPubKey)

Yes, of course, sorry.

If we can make the size of utxo entry a constant (as suggest by TierNolan) for any type of utxo, this could be simplified to


All UTXOs are considered to be potentially spendable, unless proven otherwise

I think having an exact definition of unspendable is ideal.  This is necessary for UTXO set commitments, since unspendable outputs should not be entered into the UTXO set.

At the moment, CScript.IsUnspendable() is true unless the script starts with OP_RETURN.

I think the disabled (https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L279) opcodes are OK unless they are part of an executed branch?

Are scriptPubKeys always accepted as long as they encode a byte array?  Is there a check that it is valid script when decoding?

The easiest is just to use OP_RETURN at the start to mark unspendable.  The next easiest would be if any of the disabled opcodes (or OP_RETURN) occur outside an OP_IF OP_ENDIF portion of the script.

I'm not sure how accurate https://en.bitcoin.it/wiki/Script is. In my understanding, the following codes will fail the script, even if they occur in an unexecuted OP_IF branch

RETURN, CAT, SUBSTR, LEFT, RIGHT, INVERT, AND, OR, XOR, 2MUL, 2DIV, MUL, DIV, MOD, LSHIFT, RSHIFT, VERIF, VERNOTIF, 0xba-0xff

Looking at the source code (https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L265).

The sequence is

fExec is set (true means next opcode is executed)

opcode fails to parse (only fails for double sized opcodes) -> FAIL

last push to stack to large -> FAIL

check number of non-push opcodes > maximum -> FAILS

OP_<disabled> -> FAIL

if (fExec || opcode is an IF-type opcode)
   // No curly brackets unfortunately
   case
   OP_VERIFY:  FAIL if not true
   OP_RETURN:  FAIL
   (and all the normal opcodes)

The disabled opcodes are hard FAILS no matter what happens with OP_IF.  OP_RETURN only fails if executed.

Easy rule would be that a script is unspendable if it contains a disabled opcode or OP_RETURN before the first OP_IF.  It is much easier to just check if the first opcode is OP_RETURN.

Personally, I would like to keep hope that the disabled opcodes will be re-enabled eventually :).

There is no point to "re-enable" a code because that's a hardfork. If we are going to re-introduce codes like OP_CAT, the most likely way is to softfork with P2SHv2 or OP_EVALv2

Unless P == NP, unspendability is undecidable in the general case... someone can always write a script whos spendability can't be decided without insanely large work, if they want. (e.g. push zeros, OP_SHA1 OP_EQUALVERIFY ... does the all zeros sha1 have a preimage?)

So once you're depending on their cooperation, defining a single known unspendable kind seems reasonable. Someone who wants to bloat the utxo set with an unspendable output always can; unfortunately.

Thats not much below the current system. Value and outpoint index are compressed and just take a couple bytes, the scriptpubkey is template compressed and takes 20 bytes for most scriptpubkeys. The version, height, coinbase flag, and txid is shared among all outputs with the same id. :)

I'd previously suggested something similar (using a permutation) to encrypt the utxo data locally; to reduce problems with virus data in the UTXO triggering AV and the risk of committing a strict liability crime storing someone elses data in the UTXO set.  Especially considering how small a compact encoding is, I'm not sure that doing something where one must repeat the scriptpubkey across the network (to provide the preimage) is a real win. Bandwidth seems likely to be in shorter supply than even fast storage.

I don't think collisions are even harmful; so long as they're unpredictable by an attacker.  Well I suppose I could just flood you with invalid transactions knowing that after enough one would collide for sure and you'd allow it. Then you'll go mine a bad block and fork yourself off-- but that scales exponentially with the data size, it's a multiway second preimage problem. So even a 64 bit value is pretty hard to hit. Tricky, against 10M UTXO, with a 64bit hash, the expected number of bad transactions to get a hit is 10,000 bad transactions per second for about 2135 days.  So long as you're sending the preimages though the amount stored doesn't need to be normative; increasing the size to 72 bits makes it look quite a bit less feasible.


This is much larger than the encoding we currently use.


Having multiple limits makes the linear programming problem of deciding which transactions to include much harder (both computationally and algorithmically); it also means that a wallet cannot precisely set a fees per byte based on the content of the transaction without knowing the structure of all the other transactions in the mempool.

Did you see my proposal where I replace size with a single augmented 'cost' that is a weighed sum of the relevant costly thing we'd hope to limit?  (this wouldn't prevent having worse case limits in any of the dimensions too; if really needed).

There needs to be agreement on what counts as definitely unspendable for UTXO set commitments. 

Unless the script starts with OP_RETURN, it is entered into the UTXO set would be fine.

So your idea is to replace the MAX_BLOCK_SIZE with a single composite score of block size, delta utxo size, and something else?

Yes (something else would be the sigops limit; though sigops actually have a kind of quadratic cost, due to the cost of rehashing the transaction and all its inputs; but all this only need to be very roughly correct in order to get the behavioral incentives (don't use frivolous sigops!) right).

I think the relationship is:

block size => bandwidth and storage cost
utxo size => RAM cost
sigops => CPU cost

Then the formula has to be reviewed regularly (i.e. having hardfork regularly), depending on each component's development in the real world.

However, my impression is that the CPU cost is negligible comparing with bandwidth, storage and RAM and the sigop limit is there just as an anti-DOS mechanism

No the UTXO isn't in ram, it's just more storage; it's more costly because every verifier must have it online where as the majority of nodes can forget all the rest once its burred; and certainly doesn't need to access it. I'd suggest thinking about it as storage which is necessarily online for the UTXO and storage which is mostly offline/nearline for the history, once you're past the most recent couple hundred blocks or so.
It's not exactly negligible; especially when one considers the cost of catching up-- there its the dominating cost currently for many people due to sig operations syncing the chain only runs at about 11Mbit/sec or so on a 3.2GHz quad core... (Well, libsecp256k1 will make this considerably faster-- but still slower than high speed consumer broadband that is widely available)  It only doesn't impact block propagation because virtually all signatures are cached from the initial txn relay now.

I don't really think it needs to be adjusted often (or hopefully ever); in that it can be set pretty conservatively and the most important point is getting a situation where "I will pay less fees if I do bar, so if I'm otherwise neutral I should choose to do so."-- partially this is because you're right that it's mostly an anti-dos mechanism.

Do you document your formula somewhere?

It was on the mailing list (http://sourceforge.net/p/bitcoin/mailman/message/34097489/).

Some further thoughts for comment...

Given a delta uxto size (whether composite with sigops or not), is it better to:

credit or debit the required fee during tx preparation
  or
aggregate delta utxo size at a block level and scale an "allowed" block size which can be mined for the given tx set in it
  or
both?

Considering how the utxo set is expanding so fast, would it be wise to look at changing the fundamental basis for free tx, from days-destroyed to negative delta uxto size? This could be implemented much sooner than changes associated directly with the block limit.

I created a draft BIP (https://github.com/TierNolan/bips/blob/extended_transactions/bip-etx.mediawiki) relating to etx and eblock messages.

If a protocol version number was used, then a new block message name is not strictly required.

The updates to the reference client may not be that difficult.  Transactions could be stored internally in the new format and translated when sending/receiving from the network.

To support legacy blocks, the entire blockchain would have to be reindexed.


I think setting a required fee as a network rule is the wrong approach.  Either have the UTXO limits as a separate rule or folded into size.  That way there is some kind of market price effect.

I think it's a good idea and should have an new thread for that.