Some Blockchain Ideas

Some BlockChain Ideas

I've been worried about Bitcoin scalability for a while - not only storage, but network traffic. The mantra appears to either be "we'll deal with it later via technology" (aka the Julian Simon approach) or there'll be some major players and everyone else will be running thin clients. The latter is the only way the whole thing can work, but I don't like centralizing trust. There can, of course, be mixed clients which store some complete blocks but operate mostly as a thin client. With enough of these, there would continue to be a distributed blockchain with client verification. This is the approach I favor but I'd like to make the blockchain as small and thin-client verifiable as possible.

To prevent being flooding the network with traffic, I propose having multiple channels - for both thin and thick requests.
I'd also like to see offline transactions.

Downloading the blockchain from the beginning is a pain, I'd rather clients started with a relatively recent block and then worked backwards to a point of high confidence.

Disclaimer

I'm speaking from a partial position of ignorance. Some or most of the script items I've listed below already exist. The important thing I want to outline in this document is the rough approach.

Changing the Block Chain

I propose the following changes to the block chain's data representation:

Increasing the block header from 80 bytes to 123 or 155 bytes
Adding a summary section which thin clients can request. This acts as a "medium" thickness. Most often this won't be needed.
Storing inputs and outputs, not transactions as the primary object.
Adding a execute and lock script commands

Changes to the Header

I propose the following header fields:

Field	Size	Description
version	2	The version of the block as an unsigned short
index	8	The index of the block as an unsigned long
previous_hash	32	The hash of the previous block
inputs_root	32	The merkle root for the inputs in the block
outputs_root	32	The merkle root for the outputs in the block
messages_root	1 or 33	The hash of all messages, 1 byte if there are no messages
difficulty	8	The difficulty of the block
nonce	8

There are no more trees in the header and the transactions have been moved from a combined transaction tree into two separate trees.

The Summary Section

To enable thin clients to do their own checking, a summary section is proposed. This contains the input and output nodes lists as well as the message list.

The message list is ordered and contains no duplicates. All entries are a maximum of 33 bytes.

Byte	Description
1, highest order bit	Whether or not the item is the last in the list
1, lowest 5 bits	The length of the item
2-33	The message data

The input and output nodes contain both value and hash as well as the level of the tree it is in. This allows broadcasting of trimmed trees or, in the case of full trees, only the leaf nodes. All nodes of a certain level are ordered. Trims appear between nephew nodes.

For instance:

[
    { level: 3, hash: ..., value: 18954700 },
    { level: 3, hash: ..., value: 99000000 },
    { level: 2, hash: ..., dup: true },
    { level: 3, hash: ..., value: 50000000, dup: true },
]

The above completely represents a 6 input tree with 2 inputs spent in a future block. The hashes of all level 3 nodes will be in ascending order.

The hashes for the lower level contain values, none of the other ones do. The root level is never included as it's already present in the header. If dup is set to true, the node is duplicated directly next to the instance. The hash of any node with a value is the has of the item AND its value. The has of any other node is just a hash. Nodes have the following structure:

Byte	Description
1, highest order bit	Whether or not this is the last item in the list
1, second highest order bit	Whether or not this item has a value
1, third highest order bit	Whether or not this item is duplicated
1, lowest 5 bits	The level of the item (2-31)
2-33	The hash
34-41	The value if necessary

The Transactions

Transactions are no longer bound together in a structure. All inputs and outputs appear in their own sections and are bound together by a hash. All inputs containing hashes of outputs not found cannot be included in the block. All outputs with hashes not corresponding to any input cannot be included in the block.

A JSON representation of the transactions section would looks something like:

{
"inputs":
[
    // there can only be one input with the block number of the current block, this is the mining reward
    // the block will be rejected if the value is greater than the reward + inputs - outputs
    {
        "block": 8888,
        "value": 5000000000,
        "key": null,            // null keys are allowed on any input
        "condition": ...
    },
    {
        "proof_of_presence": [ ] // this field is completely optional and is not relayed
        "block": 8120,
        "value": 95000,
        "key": ...
        "condition": ...
    }
    ... etc ...
],
"outputs":
[
    {
        // the hash is not relayed because it can be computed from the value and condition
        "value": 5000000000,
        "condition": ...
    }
    {
        "value": 900000,
        "condition": ....
    },
    {
        "value": 100000,
        "condition": ....
    }
]}

The fields for an input are:

Field	Size	Description
value	8	The value of the input
condition	variable	The condition which must be satisfied to consume the input
key	variable	Script data prepended to the condition and executed to unlock the input
block_index	8	The index of the block this input appears in. Only one input can have a number equal to the current block.
proof_of_presence	variable	trimmed tree data to prove that the input is in a certain block

The hash of an input is computed by appending the value and block to the condition and SHA256ing the bytes. Other fields are ignored in hashing. Either the key or condition may be null (empty) but both cannot be null or the input will be unspendable.

Proof of presence is optional and primarily for offline transactions or for obtaining increased client thinness (by allowing them to prove the coin's validity solely from the header rather than the header+summary). Clients may ask for a proof of presence for direct transfers. Miners will discard it.

Outputs have the same fields as inputs except they do not have block_index or proof of presence. Hashing works by appending the value to the condition and hashing.

Scripts and Offline Value Transfer

An execute script command is proposed which would pop the first item off of the stack and then convert the data there into a script which is executed in the context of the stack. Additionally a lock script command is proposed which prevents the execution of additional commands while leaving the stack intact.

Instead of evaluating to true to consume the input, the outputs which can consume a given input must have a hash which matches one of the items remaining on that input's stack after execution. That is, if an input is evaluated and leaves [ hashA, hashB ] on the stack, then it can be consumed by an output having hashA or hashB. Inputs can be consumed by multiple outputs so long as the outputs' combined value is not greater than the input's value. An example script follows:

Condition: "PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE"
Key: "PUSH { PUSH 8f1aeed82d02db7569e7d77a50a0a334a7004faf3125dca12b44e9da54a5d2a4 PUSH 75a0acb3e7149565bd57e372de76979e4a28102742a6856fa461fe406ee71e32 LOCK } DUP PUSH Gzv4b7DrQfMfXrQJT+3kqbCJHdaOeCaFkxtfRmYQmEvr7Mitpw2rxA1CdsM9ofApn/UyO5hW/fBDqmo3fp79m2s= SWAP PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4=

I propose a script command called popverify {x} which performs VERIFY PUSH {x} EQ POPTRUE

Script	Stack
PUSH { PUSH 8f1aeed82d02db7569e7d77a50a0a334a7004faf3125dca12b44e9da54a5d2a4 PUSH 75a0acb3e7149565bd57e372de76979e4a28102742a6856fa461fe406ee71e32 LOCK } DUP PUSH Gzv4b7DrQfMfXrQJT+3kqbCJHdaOeCaFkxtfRmYQmEvr7Mitpw2rxA1CdsM9ofApn/UyO5hW/fBDqmo3fp79m2s= SWAP PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4= PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE
DUP PUSH Gzv4b7DrQfMfXrQJT+3kqbCJHdaOeCaFkxtfRmYQmEvr7Mitpw2rxA1CdsM9ofApn/UyO5hW/fBDqmo3fp79m2s= SWAP PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4= PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	{ PUSH 8f1 ... }
PUSH Gzv4b7DrQfMfXrQJT+3kqbCJHdaOeCaFkxtfRmYQmEvr7Mitpw2rxA1CdsM9ofApn/UyO5hW/fBDqmo3fp79m2s= SWAP PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4= PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	{ PUSH 8f1 ... } { PUSH 8f1 ... }
SWAP PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4= PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	Gzv... { PUSH 8f1 ... } { PUSH 8f1 ... }
PUSH G97SWeW/07qkKKfDEvSfJVRQT9Jwz3vGFmtN8NiehA9sBJWBYco7YJYbV+QcmBMRC1EPFJmg5/BD8VMGrCgT/u4= PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	{ PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
PUSH Cash in my hand is great VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	G97... { PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	Cash... G97... { PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	17mD... { PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
EQ POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	17mD... 17mD... { PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
POPTRUE VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	true { PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
VERIFY PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	{ PUSH 8f1 ... } Gzv... { PUSH 8f1 ... }
PUSH 17mDAmveV5wBwxajBsY7g1trbMW1DVWcgL EQ POPTRUE EXECUTE	17mD... { PUSH 8f1 ... }
EQ POPTRUE EXECUTE	17mD... 17mD... { PUSH 8f1 ... }
POPTRUE EXECUTE	true { PUSH 8f1 ... }
EXECUTE	{ PUSH 8f1 ... }
PUSH 8f1aeed82d02db7569e7d77a50a0a334a7004faf3125dca12b44e9da54a5d2a4 PUSH 75a0acb3e7149565bd57e372de76979e4a28102742a6856fa461fe406ee71e32 LOCK
PUSH 75a0acb3e7149565bd57e372de76979e4a28102742a6856fa461fe406ee71e32 LOCK	8f1a...
LOCK	75a0... 8f1a...
No further commands can be appended or run	75a0... 8f1a...

The input in this example leaves two hashes on the stack which outputs with that condition/value hash can consume. ALL hashes left on the stack must be consumed by outputs in the same block or inclusion of the input will invalidate the block. Orphaned outputs will also invalidate the block.

Note that the message to verify can be anything which allows in-block information without the need to generate lots of addresses to keep track of things.

Offline Transactions

To reduce load on the network, bitcoins can be passed directly between individuals through off- or alternate-network channels. A signer can change the executable (s)he pushes onto the stack to allow another person to consume the input. The person who transmits the coin to the bitcoin network should lock the script so miners can't replace the outputs with their own outputs.

The person receiving the signed coin is still under the threat of a double-spend from the sender, but can easily verify both the presence of the coin by getting the summary of the block of the coin (or, if proof of presence is provided, merely the header of the block of the coin) and then checking summaries to ensure that the coin was not consumed elsewhere.

Thin Client Observation

Messages probably aren't necessary but can provide a way for thin clients to look for transactions solely from summary traffic. Ultimately it reduces the need to relay large amounts of data by allowing clients to only focus on blocks containing messages for them. If things get too spammy, miners can raise the cost of including messages.

Messages are included with a message script command which is not added to the stack but instructs the miner to include the message in the block (if it's not there already).

Conclusion

The goal of proof of presence and the breaking transactions into inputs and outputs is to reduce storage and network requirements. Let the holders of coins prove their coins are valid rather than relying on miners and others to store all of that data. Without storing all data, miners could potentially mine invalid blocks. However, if just a few nodes at a time verify blocks and spread messages of invalid blocks to other bitcoin nodes, good blocks will still outpace bad blocks.