Very interesting. I spent some time trying to figure out a claiming process using OP_RETURN but I couldn't get the details sorted out. I'd love to hear your ideas.
Here is a very rough draft (more like putting an idea on a napkin at this stage)
Note: As the current time the draft limits itself to an alternate verification method for claims. In the future if Peter sees continued merit, this entire draft would likely be a subsection of a general spinoff whitepaper.
Some useful references:
Original spinoff proposal by Peter RBitcoin whitepaper by Satoshi Nakamoto (see section 8 on SPV clients and section 10 on attack chain calculations)Analysis of hashrate-based double-spending by Meni RosenfeldProposal for a Simplified Claim Verification (SCV) ModelIntroductionThe SCV (Simplified Claim Verification) is an alternate method of verifying spinoff claims which uses the parent chain to perform signature validation. The original claim verification method outlined by Peter R could in comparison be described as a full claim verification. The differences between these two models has some similarities to the differences between how full nodes and SPV (Simplified Payment Verification) clients validate transactions on the Bitcoin network. The full claim verification requires spinoff clients to implement cross chain validation, the clients are larger and heavier but they have no outside dependency. The SCV model is tradeoff by removing the validation of parent chain signatures from the spinoff in exchange for a dependency on the parent blockchain. This dependency can be temporary through the use of claim window.
The full verification model involves the claimant signing a claim message using a parent network client or tool and then submitting the digitally signed claim to the spinoff network. The spinoff network matches the claim against a ledger created from the unspent outputs of the parent network. Some outputs are relatively simple. The "normal" Bitcoin transaction is a Pay2PubKeyHash. The output contains a PubKeyHash and a tx spending that input (or message assigning a claim) needs to be signed by the private key of the corresponding PubKey which hashes to the PubKeyHash in the output. Bitcoin (and other potential parent chains) have more complex scripts and this complexity is increased by the fact that the output mut ay define multiple signatures or other conditions. In some cases the output does not contain the script but instead a hash of the script (P2SH). This means even a full parsing of the blockchain can not identify all possible script templates. To be handle the redemption requirements of all claimants the spinoff would need to reproduce most or all of the transaction validation engine of the parent chain inside the spinoff client. If the parent chain is Bitcoin, and the spinoff is very Bitcoin like this may not be a significant overhead but that is also the scenario that is the least interesting. A spinoff which is radically different would end up maintaining a large amount of code which is only used for claim processing.
The SCV model like SPV model is a simplified verification process, that relies on assumptions that can be made when a transaction is deep in the best chain of a the blockchain. A spinoff using the SCV model can without any direct knowledge of how the parent validates txs rely on the fact that an invalid tx deep inside the longest chain of the parent blockchain is not possible unless a majority of the computing power on the parent chain is either malicious or non-compliant (protocol flaw).
As transaction validation on a single network is an easier concept, lets look first at how SPV clients on the Bitcoin network use tx depth as a proxy for direct validation. In the Bitcoin network the input of a transaction contains a reference to the unspent output of a prior transaction. SPV clients do not maintain a full copy of the blockchain so while an SPV client can verify the referenced output is valid it can't determine is they are spent or unspent. The SPV security model relies on the the fact that building an alternate blockchain is an expensive task and compliant nodes will not extend a chain with an invalid block. If a tx is invalid (i.e. the inputs reference an otherwise valid but already spent output) then the block containing it is invalid as well. Full nodes that block and build off the best valid chain. So a tx which is hundreds of blocks deep in the best chain of a blockchain can be assumed to be valid unless an attacker has a majority of the computing power (51% attack) and even in that case the cost of the attack and the fact that it would only fool SPV clients makes it an attack vector of limited value.
In the SCV model, the claimant creates a tx which contains an output with claim instructions for the spinoff. The parent network is unaware of the spinoff but it will validate the tx like any other tx on the parent network. The spinoff client may not know how to validate the the parent tx but it can rely on the fact that the tx is in best chain of the parent blockchain as an indirect validation which like the SPV model is valid as long as the attacker doesn't have a majority of the computing power (51% attack) and the tx is sufficiently deep that it would be infeasible to out build the majority of the network for a chain that long. The spinoff client only needs to be able to extract the identity of the signer from the inputs and compare them to the claim identities recorded in the bootstrap.bin.
Definitions (some new concepts are introduced so I found it useful to define some new terms to avoid lengthy in-line explanations)Parent - The network from which the claims to the spinoff distribution are produced from (i.e. parent block and parent tx refer to txs and blocks which are part of the parent network).
Spinoff - The network being bootstrapped by the parent network. In SCV model there is a dependence by the spinoff on the parent network (i.e. spinoff block and spinoff tx refer to txs and blocks which are part of the spinoff network).
SCV - Simplified Claim Verification. An alternate to full validation of the parent signatures by the spinoff network.
Dual Network Access - A node which has access to both the spinoff and parent network. In the SCV model not all of the nodes need dual network access but at least some portion of the miners will.
Single Network Access - A node which has access to only the spinoff network. The SCV model allows all nodes (even those with
Claim Payload - A sequence of bytes located in an unspendable output on the parent network which carry instructions for redeeming a claim on the spinoff network.
OP_RETURN - An opcode in the Bitcoin (and some alt-coins) which allows embedding a 40 byte payload in an unspendable output. OP_RETURN provides a method for embedding the claim payload in the parent chain in a manner that ensures it can be pruned.
Claim Request Tx * - The tx on the parent network which contains the Claim Payload.
Claim Redemption Tx * - The tx created on the spinoff network which allows the redemption of a claim in a manner that can be validated by nodes even those with single network access.
Mature - The spinoff network requires that parent blocks and tx be mature before they can be processed by the spinoff network. This is done to improve efficiency and increase the cost and reduce the probability of a successful forgery.
Merkle Branch - A structure used to validate a single element of a merkle tree without need for the entire tree.
Snapshot Block - A block designated in the parent network that is the basis for creating the ledger of valid claims. In SCV the block header of the snapshot block forms the root of the parent chain recorded by the spinoff.
Claim Window - An optional concept which designates a block height on the parent chain beyond which no claim request txs are valid. This puts an upper bound in the dependency of the spinoff on the parent network.
As already proposed in this thread the bootstrap.bin will contain a ledger of "claims" against the spinoff based on the unspent outputs of the parent network at a designated blockheight (snapshot block). No significant deviation from the proposed format of the ledger is required to support a spinoff using SCV clients.
The spinoff will need to hardcode the blockheader (80 bytes) of the snapshot block of the parent chain. It would be beneficial for the blockheader of the snapshot block to be part of the output for open source bootstrap creation and validation tools. The block header is not needed for spinoffs using full validation but the small size is negligible compared to the benefits of a single automated open source tool. The snapshot block header is the root of the subset of the parent chain required by the spinoff. The blocks prior to the snapshot are not required because the bootstrap ledger contains the value of the unspent outputs as of the snapshot block. From the context of the spinoff chain, the snapshot block becomes the genesis block for the (reduced) parent chain.
TODO: Determine the output distribution by unspent value instead of nominal number of outputs.
TODO: Determine if handling non-P2SH non-standard outputs warrants the complexity (distribution of the long tail).
TODO: Show optional method for reducing the size of native m of n outputs in the bootstrap.bin.
TODO: Show optional method for reducing the size of entire ledger by trading computing power for space.
Creating Claim Request Tx on Parent NetworkThe claimant begins the process by creating a Claim Request Tx on the parent network. The tx consists of one or more inputs signed by the same identity as an unredeemed claim in the bootstrap ledger. The tx can have one or more non-claim (standard) outputs. This is necessary to "spend" the value of the unspent output(s) referenced in the input(s). So far this is a "normal" transaction on the parent network however an additional OP_RETURN output with a zero value will be added. OP_RETURN outputs are not spendable on the parent network but allow an arbitrary payload limited to 40 bytes. OP_RETURN is prefered over other ad-hoc solutions as the OP_RETURN output is marked by the parent network as unspendable. It doesn't bloat the UXTO and can be optionally pruned by nodes on the parent network. If it important that the OP_RETURN output have a zero value and the sum of the values for the other outputs equal the sum of the values of the inputs (minus any tx fee) to avoid losing funds on the parent network.
The 40 bytes recorded in the OP_RETURN output is the Claim Payload; it embeds spinoff specific instructions inside an otherwise normal tx on the parent network. The Claim Payload should contain a "magic bytes" header to allow rapid identification of Claim Requests by the spinoff network, spinoff specific identifier indicating the identity/account/address that is encumbering the claimed coins, and optionally a fee paid to spinoff miners. It is important to note the Claim Payload has no significance to the parent network. It is just a blob of data outside the scope of the parent network (and one which may be pruned in the future). The parent network is validating the larger Claim Request Tx. The limit of its validation of the OP_RETURN output is to ensure it meets the limits specified by the parent protocol (for example in the Bitcoin network the embedded data in an OP_RETURN output is limited to 40 bytes, and a transaction is limited to a single OP_RETURN output). The parent network can not validate the Claim Payload, that is a task for the spinoff network.
Validating the Claim Request By Proxy (simplified)Before moving forward lets assume a simplified scenario where all nodes on the spinoff network have a complete continually updated copy of the parent blockchain. This would be an excessive requirement and one that can by removed but it allows for a simplified explanation of how the Claim Requests can be validated without directly verifying the signature. Once a node on the spinoff network validates that the Claim Request Tx is sufficiently deep in the longest chain of the parent network it can conclude that the tx was properly signed even without verifying the actual signature (and all the complexity and overhead that entails). What allows that assumption?
If the tx was improperly signed, then the tx would be invalid. An invalid tx included in a block makes the block invalid. Any block built on top of an invalid block is likewise invalid. Compliant nodes would reject the invalid block and build off the last valid block.
So lets look at three different scenarios:
a) The tx is improperly signed (a forgery) and the forger has no hashrate on the parent network. The tx is dropped by all full nodes and if it reaches a miner, no compliant miner includes the tx in a block as it would make the block invalid. Once the tx is included in any valid block on the parent network the spinoff can conclude this is not the case.
b) The tx is improperly signed and the forger has a minority of the hashrate on the parent network. The forger could include the invalid tx in a block but other compliant miners would see that block as invalid and not extend that chain. The attacker by luck could temporarily produce the longest chain but the deeper the tx is in the longest chain the lower the probability that an attacker with a minority of the hashrate could extend a chain longer than the compliant miners. Even if an attacker has 40% of the hashrate on the parent chain, the probability that the attacker will have the longest chain after 89 locks is 0.1%.
c) The tx is improperly signed and the forger has a minority of the hashrate on the parent network. Given enough time the probability the attacker will have the longest chain approaches 1. This would be a variant of the 51% attack however the cost can be made prohibitively expensive. In a conventional double spend attempt the attacker is replacing one valid tx with another valid tx. If the attacker is successful he double spends the victim and since his chain is the longest he claims the block rewards as well. The value of the block rewards offsets the cost of the double spend attempt. However in a SCV claim forgery the tx has an invalid signature. The blocks created by the attacker will always be invalid on the parent network. The attacker can only use that chain to spoof the SCV validation. Even in a successful claim forgery the attack will lose the value of the block rewards on the parent network. The cost of the attack is unavoidable. Since a claim request only occurs once, that cost can be made prohibitively high for an attacker by requiring an increased number of confirmations (depth in the parent blockchain) before the Claim Request is considered valid. As an example if using the Bitcoin as the parent network, the approximate value of the block rewards paid to miners is currently $2.3M per block day (144 blocks). By requiring a Claim require 3 block days (432 confirmations) to mature even a successful forgery would cost the attacker more than almost $7M in lost rewards on the parent chain.
In this simplified model we assume that all nodes on the spinoff network have the full blockchain of the parent network. We have shown that if the Claim Request Tx is not orphaned and sufficiently deep in the parent blockchain then the Claim Request Tx can be assumed to be properly signed unless the forger has a majority of the parent hashrate (51% attack) and a willingness to accept an extremely high irrecoverable cost in lieu of easier and more profitable attacks on the parent network (i.e. double spends against crypto currency exchanges). The cost and complexity of building a long flawed chain is used as a proxy instead of full validation a the transaction. This is very similar to how SPV clients operate although the specific elements of what is verified by proxy are different. The SCV model would not be very useful if all nodes had to maintain a full copy of the parent blockchain however this simplified model is easier to explain. The next section shows how the tx can be verified by any node on the spinoff network without access to the parent chain.
Validating the Claim Request By Proxy (actual)In order for the spinoff network to validate the claim redemption tx it must confirm the following
1) The the claim_tx (contained in the OP_RETURN output) in the parent chain is properly formatted and otherwise valid.
2) That at least one of the input(s) of the parent chain chain has the proper signer and is not a double claim
a) for Pay2PubKey tx = extract the PubKey, hash it, and compare to bootstrap.bin
b) for Pay2PubKeyHash tx = extract the PubKey, hash it, and compare to bootstrap.bin
c) for Pay2ScriptHash tx = extract the redeemScript, hash it, and compare to bootstrap.bin
d) for native multisig tx = extract the PubKeys, arrange in canonical order, hash it, and compare to bootstrap.bin
3) That the tx is located in a valid Bitcoin block (blockheader, merkle branch, and txid can be used to prove this)
4) That the block can be linked to the "bootstrap snapshot block in the bootstrap.bin
All of these should be pretty self explanatory except #4. The spinoff will need to be able to perform SPV level block verification (header only). A copy of the block headers for the parent chain from the spinoff block to the closing of the claim window will need to be available to nodes on the spinoff network.
For this reason this method of bootstrapping makes the most sense when the spinoff is being merged mined and has a claim window however it could be used on any network but at a minimum some miners would need to have dual network access (parent and spinoff). The simplest method to record the bitcoin blockheaders into the spinoff chain would be to have an optional field in the spinoff blockheader for recording the bitcoin/parent blocks which are "mature" since the last spinoff block. Other nodes do not need bitcoin/parent network access. They are only validating that the blockheaders are valid not that they actually occur on the bitcoin network. Some block validation rules will need to be developed, namely to reduce the orphan chains which are recorded in the spinoff only "mature blocks" are recorded. This can be verified by requiring bitcoin blocks to be a certain number of seconds older than the timestamp in the spinoff block. Since timestamps can be loosely verified (network median time) this ensures that only "old" (and thus very unlikely to reorg) parent blocks are recorded. As an example if the network intends to consider bitcoin blocks more than 288 blocks (2 block days) deep in the chain as "mature" then the spinoff could require the timestamp of the bitcoin block be more than 288*600 = 172,800 seconds earlier than the timestamp of the spinoff block.
Bridging the parent and spinoff networkThe claimee creates a Claim Request Tx on the parent network. The Claim Request Tx exists only on parent network. The information in that tx (inputs and the Claim payload) combined with parent blockheaders recorded in the spinoff blocks allow the construction of the Claim Redemption Tx (existing only on spinoff network). One important factor is that construction the Claim Redemption Tx requires Dual Network Access however validating a Claim Redemption Tx only requires access to the spinoff network. That is the key to the security model. By ensuring that single network nodes can still validate all txs (including Claim Redemption Txs) the peer to peer nature is preserved and there is no reliance on trusted "super peers".
The SCV model does require one or more entities need to have Dual Network Access to act as a bridge between networks. Without these bridge nodes the spinoff network will never become aware of the Claim Requests (as they exist on the parent network). The bridge nodes can not alter or forge redemption txs. A bridge node is limited to refusing to relay information from the parent network and this withholding attack would only be effective if all bridge nodes engaged in withholding. There is no special cost in running a bridge node beyond the resource requirements of each network so the attack would not be very effective. Miners are a logical choice to act as a bridge node but as a fallback non-mining nodes can also act as a bridge.
Dual Network Mining Nodes: Spinoff miners who have dual network access can construct the Claim Redemption Tx (part of spinoff network) by identifying Claim Request Tx (part of the parent network). The Claim Tx can be constructed in a deterministic and trustless manner by any party with Dual Network Access. The instructions in the claim payload of the claim request made by the claimee on the parent network ensure that a miner can't modify a request as the tx would be invalid. The claimee doesn't need to do or submit anything on the spinoff network (the Claim Reward Tx doesn't need to be signed as it is similar to a Bitcoin coinbase tx except the output is constrained by the instructions in the Claim Payload. Miners with dual network access will need to parse the blocks of the parent blockchain, located Claim Request Txs, construct the Claim Redemption Txs, and record them in blocks on the spinoff network. There should be sufficient incentive (in the form of tx fees possibly subsidized as a tx reward similar to block reward in the Bitcoin network) for some miners to maintain dual network access. Miners opting to run dual networks would not be required to broadcast these Claim Redemption Txs before including them in a block and thus it would be in their best interest to include them in the next block as a source of additional fees.
Non Mining Bridge Nodes & Single Network Miners: If the Dual Network miners fail to include Claim Redemption Txs in spinoff blocks in a timely manner non-mining "bridge nodes" (possible setup as a fallback by the developer for the public good) could parse the parent blockchain, construct the Claim Redemption Tx and broadcast the txs to peers who would validate and relay them like any other txs, and the tx would eventually be included in a block by Single Network miners. It is probably unlikely this would be needed, but it illustrates that the miners who have Dual Network Access can't do anything malicious with that access. At best they may learn of Claim Requests before other nodes and can include them in a block for additional fees but the value of that knowledge rapidly declines. To encourage dual network mining, the bridges could operate on a delayed fashion waiting a few blocks beyond when a Claim Request is mature. This would give dual network miners, "first chance" at those fees, creating a built in incentive while preventing any type of cartel behavior as the information only has "value" if acted upon immediately (before all nodes learn of the new txs and their fees).
Recording the Claim Redemption Tx in the spinoff blockchainIt is important to keep in mind that the Claim Redemption Tx will exist only on the spinoff network and the spinoff network may be radically different than the parent network. It is thus beyond the scope of the spinoff concept to define the exact claim redemption format (for example txs on a network using ring signatures or zero knowledge proofs would look radically different than "Bitcoin txs". Whatever the format used there are data elements required to ensure that the Claim Redemption Tx can be validated by single network nodes. The raw Claim Request Tx (pulled from parent network), the block hash of the block containing the Claim Request Tx (on the parent network), and a merkle branch are required. How these elements are used to validate the Claim Redemption is described below.
Example Claim Redemption Tx (actual redemption tx will vary based on the constraints and design of the spinoff network)
TxHeader *
Parent_tx - Tx containing the claim payload (also called the Claim Request)
Parent_block_hash - Hash of the block on the parent network that contains the parent_tx
Parent_merkle_Branch - Allows cryptographic validation that the parent_tx is located is part of the merkle_tree in the parent block without the full merkle_treemerkle_tree
Inputs *
[0]
Claim_Id - Claim_Id for the zeroeth identity extracted from parent_tx input(s)
[1]
Claim_Id - Claim_Id for the first identity extracted from parent_tx input(s)
...
[n]
Claim_Id - Claim_Id for the nth identity extracted from parent_tx input(s)
Outputs **
[0]
Spinoff_output - Computed from the claim_payload
Value - Computed from the sum of the value of the claim_ids with possible modification based on protocol rules or instructions in the claim payload (miner fees, etc)
* Recording inputs is not required (similar to how there is no requirement for coinbase tx to show the "input value") the "inputs" are extracted from the inputs in the claim_request and validated against the unredeemed claims in the bootstrap.bin. Explicitly recording these inputs may be useful for optimizing the "unredeemed claim set" (similar to the UXTO in Bitcoin network).
** The exactly output structure will depend on the requirements and constraints of the spinoff network. The format and required elements of the claim payload will work in conjunction with the output to ensure the value is secured by the claimee. For a c
Pseudocode for validating the Claim Redemption TxRequired:
Spinoff nodes is well connected to peers.
Node has a full copy of the spinoff blockchain according to peers.
Node has constructed a "unredeemed claim set" which is a subset of the bootstrap.bin excluding all claims which have already been redeemed.
Node has constructed a header only subset of the parent_blockchain by extending from the snapshot block using parent_blockheaders located in spinoff blocks.
Perform the following:
1) parent_block_hash = H(parent_block_header) per parent tx rules
2) parent_txid = H(parent_tx) per parent tx rules
3) Parse input(s) based on known templates, identify the signers, and match against the set of unredeemed claims. The inputs[] = set of unredeemed claims matching input signers.
4) Extract claim_payload from parent_tx.
5) Compute c_merkle_root using the tx_id and merkle_branch.
Claim Redemption is valid only if all the following are true:
1) The parent_block_hash is located in the parent_blockchain constructed from parent_blockheaders in spinoff blocks.
2) The parent_block_hash is not part of the best chain or is not sufficiently deep in the best chain.
3) The c_merkle_root is the same as the merkle_root recorded in the parent_block.
4) The inputs[] is not null and the value of the output is equal to sum to the value of the claim inputs.
5) The claim payload is valid per the spinoff protocol and the resulting tx properly encumbers the output based to the limitations set in the Claim Payload.
Advantages & Disadvantages of SCV ModelPRO: The parent tx validation complexity is removed. The spinoff doesn't perform a validation on the Claim Request Tx containing the claim payload (this is done by the parent). The spinoff does needs to be able to identify the Claimee and match it against the authorized claims in the bootstrap.bin by extracting the unique identifying criteria from the input(s) of the Claim Request Tx. The scope of this problem is significantly smaller than understanding the full validation rules in all possible permutations of the parent chain.
PRO: More than 99.9% of outputs can be categorized into less than 30 variations of 5 basic templates which reduces the code overhead imposed by the parent on the spinoff. It is possible that 100.00% of potential claims could be validated with a significantly smaller bootstrap.bin and less code overhead than what would be required for a "full validation" claim redemption model. **
PRO: Spinoff network doesn't need to interpret the redeem script (P2SH) which makes compatibility easier to assure because P2SH scripts are unknown until spent
PRO: Miners can handle the seamless transfer of claims from parent network to spinoff
CON: This requires the spinoff to record all blockheaders of parent chain from the snapshot block forward until all claims have been redeemed. This is unlikely to ever occur unless a claim window is designated.
CON: Security model is different but comparable to SPV clients not full nodes. The risk is moderated by using a parent network with very high mining difficulty/cost and requiring long maturity of parent blocks to make forgeries prohibitively expensive.
CON: Requires at least some but not all nodes to have dual network access (to transfer blocks and claim tx from parent network to spinoff network. the effect is reduced if the network is already merge mined)
** TODO: Replace with distribution by unspent output when available.
Poll
