Spin-offs: bootstrap an altcoin with a btc-blockchain-based initial distribution

[darkmatter7]

This is a very interesting distribution mechanism.  I will be reading more throughout the day.

[alexkravets]

Mr. Darkmatter,

See some of the reasons for why this distro mechanism is the *least bad one* in the post above
https://bitcointalk.org/index.php?topic=563972.msg7676923#msg7676923

[gatra]

I have the feeling that you are overthinking this....
Just allow PubKeyHash tx only, and use bitcoin signed messages for claiming. And announce with some time so interested parties can momentarily send funds to a PubKeyHash if they have it in some other form.

[Zangelbert Bingledack]

I have the feeling that you are overthinking this....
Just allow PubKeyHash tx only, and use bitcoin signed messages for claiming. And announce with some time so interested parties can momentarily send funds to a PubKeyHash if they have it in some other form.

Can you elaborate on this?

[rapport]

So the official Ethereum sale has started.  When can people try out the aethereum wallet etc and see how much aethereum they have ?

[alexkravets]

Yes, this is of course THE QUESTION.

If spin-offs can be successful then there cannot possibly be a better target for a spinoff tracking clone than Ethereum.

I guess the answer to this is only known to DeathAndTaxes ... i.e. how alive is the code base behind the spinoff idea ?

Will there actually be an Aethereum at all ?

[Peter R]

UPDATE: TOTAL BOUNTY AS OF 04-07-2014 = 4.35 BTC

Peter R : 1 BTC
alexkravetz : 2 BTC
thoughtfan: 0.35 BTC
cypherdoc: 1 BTC

With the recent threads about Ethereum's pre-sale, I thought it might be a good time to bump this thread.  

I'd like to contribute 1 BTC towards a bounty for the first spin-off that achieves the following:

1. At least 1% of the valid claims (1% by amount AND by number) in the snapshot file (initial money supply) have been claimed.

2. The spin-off trades on a legitimate exchange (something at least as recognized as Poloniex, MintPal or Cryptsy).  

3. The spin-off uses the snapshot.bin file format being developed in this thread¹.

4. At least 99.9% of bitcoin wealth in the UTXO set at the block height of the snapshot file must be claimable.  

5. The spin-off may use full claim verification, simplified claim verification, or both.  If simplified claim verification is used, the time-limit must be no shorter than 1 year.

6. The developer will prove he or she is the developer by producing a bitcoin-signed message that verifies to an address embedded in the header portion of the snapshot.bin file.  


¹Since the snapshot.bin file format is not entirely complete, bounty seekers should keep us up to date in this thread so that the the final details regarding the snapshot.bin file format can be coordinated.

[alexkravets]

I am joining this bounty with 1 BTC

[Peter R]

I am joining this bounty with 1 BTC

Awesome.  I've updated my post above. 

[Peter R]

Smooth had an interesting idea that he posted to the aethereum thread. I'm cross-posting it here as it is relevant to the format for snapshot.bin.
 

Agreed.  For this reason it probably makes sense that the snapshot.bin genesis block for any spin-off contains a record of 100% of the claimable funds.  Whether 100% is actually claimable (as opposed to 99.9xxx%) is still implementation dependent, as there are some subtle complicating issues.  

Maybe a full snapshot.bin is published somewhere as a Merkle tree but only the root hash need be distributed? To make a claim you post a proof that your claim is supported by an entry in the tree.

Interesting.  

This proposal has the advantage that the spin-off genesis block is tiny in byte size and it has the advantage that the unclaimed entries in snapshot.bin need not be store in RAM on the client nodes.  A disadvantage is that the claim TXs are a lot bigger and the same inner hashes will get mined over and over (different claim TXs will share common inner hashes in their respective Merkle branches).  I see no reason why your proposal wouldn't work with both full-claim verification and simplified-claim verification.  The bridge nodes in Gerald's SCV proposal could optionally store the full snapshot.bin file so that they can prepare the claim TXs with the Merkle branch proof and then mine them into a block to earn a claim fee (assuming this fee exists).    

These are the kind of discussions we need to have to finalize the format for snapshot.bin.

[Peter R]

I have the feeling that you are overthinking this....
Just allow PubKeyHash tx only, and use bitcoin signed messages for claiming. And announce with some time so interested parties can momentarily send funds to a PubKeyHash if they have it in some other form.

Since pay2PubKey can be recast as pay2PubKeyHash, a simple "bitcoin-signed message"-based claim solution would permit 99.8421% of the valid bitcoin wealth to be claimed.  But remember this simple claim method could still be applied to a snapshot.bin file that encoded 100% of the valid wealth.  IMO, we are trying to come up with a general solution to the problem (that solves every case), and then spin-off developers can select whatever pieces of this solution they see fit.  In June, we didn't even know what % of the bitcoin wealth could be claimed with a simple bitcoin-signed message, but now we do. 

[smooth]

Smooth had an interesting idea that he posted to the aethereum thread. I'm cross-posting it here as it is relevant to the format for snapshot.bin.
 

Agreed.  For this reason it probably makes sense that the snapshot.bin genesis block for any spin-off contains a record of 100% of the claimable funds.  Whether 100% is actually claimable (as opposed to 99.9xxx%) is still implementation dependent, as there are some subtle complicating issues.  

Maybe a full snapshot.bin is published somewhere as a Merkle tree but only the root hash need be distributed? To make a claim you post a proof that your claim is supported by an entry in the tree.

Interesting.  

This proposal has the advantage that the spin-off genesis block is tiny in byte size and it has the advantage that the unclaimed entries in snapshot.bin need not be store in RAM on the client nodes.  A disadvantage is that the claim TXs are a lot bigger and the same inner hashes will get mined over and over (different claim TXs will share common inner hashes in their respective Merkle branches).  I see no reason why your proposal wouldn't work with both full-claim verification and simplified-claim verification.  The bridge nodes in Gerald's SCV proposal could optionally store the full snapshot.bin file so that they can prepare the claim TXs with the Merkle branch proof and then mine them into a block to earn a claim fee (assuming this fee exists).    

These are the kind of discussions we need to have to finalize the format for snapshot.bin.

A disadvantage of this approach is that, as you say, inner hashes are repeated.

Perhaps the two approaches can be combined.

A small snapshot.bin can be distributed, containing the outputs with the highest value or perhaps those somehow deemed "most likely" to be claimed (which might in part be a function of value, perhaps age, etc.). Those can be claimed by direct reference without a proof. For holders of the rest, a claim would need to be made using the (less space efficient) proof.

[alexkravets]

We should consider posting the bounty here https://www.bountysource.com/ seems like the most liquid / high volume bounty marketplace.

Also provides proper reference points for the appropriate reward / effort ratio given other similar C++ projects

[Peter R]

The blockchain-size implications on Smooth's proposal to hash the claim entries into a Merkle tree.  

D&T's work suggests that the UTXO set can be expressed as approximately 3 million unique claims.  To build the first row of the corresponding Merkle tree, each transaction would be hashed (e.g., by SHA256) into (e.g.) a 32-byte digest:  

Length of first row = 32 bytes  x  3x10^6 = 96 MB

The row above this one consists of half that number of hashes. Each entry is the hash of the 64-byte concatenation of the corresponding two hashes below it in the tree.  This process is continued until we arrive at the root hash:

Code:

Length of first  row  =  96 MB
Length of second row  =  48 MB
Length of third  row  =  24 MB
Length of fouth  row  =  12 MB
       ...                ...
Length of top row (root hash) = 0.000032 MB
====================================
Size of Merkle tree     192 MB

The number of rows in the Merkle tree is given by:

    1 + ceiling (log₂ 3x10^6) = 23

A claim transaction that provided the complete Merkle-branch proof would be be ~23 rows long where each row (except the root) would contain 2 x 32-byte hashes.  So the additional overhead to provide the Merkle-branch claim proof would be approximately:

    Size of Merkle-branch claim proof ~= 23 x 2 x 32 bytes = 1.5 kbytes

If we imagine that 1% of the potential claimants make a claim, the blockchain would grow (due to storing the Merkle-branch claim proofs) by:

   0.01  x  3x10^6  x  1.5 kbytes = 45 MB

Similarly, if 10% or 100% of stakes were claimed, the blockchain would grow by 450 MB and 4.5 GB, respectively.  This means that if over a few percent of claims were made, the blockchain would be bigger than it would be if the flat snapshot.bin files was stored as the genesis block.  


Additional thoughts

Hashing the claim entries into a Merkle tree and requiring the claimant to provide the Merkle-branch proof increases the size of the blockchain should a large number of claims be made; however, the big benefit is that this seems to simplify the cloning process.  It means that the clones don't need to be aware of or manage snapshot.bin.  They just need to define a new type of claim TX that verifies the signature (either using FCV or SCV) and then follows the Merkle branch down to its root and compare that to the hard-coded Merkle root.  If the signature verifies and the Merkle branch leads to the hard-coded root hash, and if the claim has not already been made, then the claim TX is valid.  But will it be more difficult for the clones to verify that a particular claim hasn't already been made using this method?

[thoughtfan]

I am joining this bounty with 1 BTC

I'll pledge .35 btc too (the same as I've just spent on 700 ETH).  I much prefer the spin-offs approach but also realise there's a lot to figure out yet. I guess cash incentive may add to the motivation of those capable of making this happen which is why I'm chipping in on this one.  So I'm backing two horses in this race And yes, I'm up for making my bounty pledge official on Buntysource or wherever

[DeathAndTaxes]

Sorry that I haven't been active in the development.  This is more for "fun" and the development which pays the bills has been taking up most of my time.  

To expand on Peter's "to merkle or not to merkle" discussion
1) Peter, a merkle branch only need one hash per level not two (the other side is computed each level from the claim txn) and a single bit to indicate if the additional hash is on the left or right).  You also don't need to include the root hash for the same reason.  If that doesn't make sense I can go into detail but I will wait to avoid a long explanation on what might just be a simple oversight.  The size of a merkle branch (in bytes) for up to 32 levels would be: branch_size = (merkle_levels * digest_size)+4.

2) The larger claimset the more the overhead.   However this is not likely to have much of an impact due to the logarithm relationship between set size and number of branches.  Until we reach more than 4.19 million valid claims the merkle branch would only need 22 segments and using 160 bit hashes that would be 444 bytes.  If more than 32 levels are needed then the size of the branch increases another 4 bytes but the number of unique "claimants" in the UTXO would need to be more than 10x the current size before that happens.

Code:

Digest Size: 32 bytes
PathMask: 4 bytes
Branch_size: 32*merkle_levels + 4

levels     claims(mil)   branch size (bytes)
20                  1                   644
21                  2                   676
22                  4                   708
23                  8                   740
24                 16                   772
25                 33                   804
26                 67                   836
27                134                   868
28                268                   900
29                536                   932
30              1,073                   964
31              2,147                   996
32              4,294                 1,028

3) Using a 160 bit hash would make the merkle branch smaller by a third.  Even smaller hash digest (100 to 128 bit) could be used but that only provides a minimal reduction in size.  The set is fixed so it can be guaranteed to be collision free.  A preimage attack against even a 100 bit reduced length hash is infeasible at the current time.  It may however make sense to benchmark the speed of various hash functions as there will be a large number of branch validation in bootstrapping nodes.   I know off the top of my head SHA-512 has much higher throughput than SHA-256 on most systems this is due to SHA-512 using 64 bit words.  NIST does rate SHA-2 to be used in "cutdown" digests (i.e. take left 128 bits) and there are no known security implications in doing so.

[Peter R]

I am joining this bounty with 1 BTC

I'll pledge .35 btc too (the same as I've just spent on 700 ETH).  I much prefer the spin-offs approach but also realise there's a lot to figure out yet. I guess cash incentive may add to the motivation of those capable of making this happen which is why I'm chipping in on this one.  So I'm backing two horses in this race And yes, I'm up for making my bounty pledge official on Buntysource or wherever

Thanks thoughtfan.  I updated the bounty post to show the new total of 2.35 BTC.  I suspect there might be some more pledges, and then perhaps we could move the pledged funds to a multisig 2-of-3 address controlled by 3 trusted members of the forum.  Refund TXs could be issued instantly for all pledges using N_LOCKTIME where N_LOCKTIME defines the deadline for winning the bounty. 

I should also point out that the bounty (at least as I specified it) did not require any particular coin to be cloned--just that the clone had to achieve sufficient adoption as evident by the number and magnitude of claims that were made and as evident by the spin-off trading on an exchange.  I suppose we could revisit the exact requirements to claim the bounty if more people are interested in contributing. 

[thoughtfan]

I am joining this bounty with 1 BTC

I'll pledge .35 btc too (the same as I've just spent on 700 ETH).  I much prefer the spin-offs approach but also realise there's a lot to figure out yet. I guess cash incentive may add to the motivation of those capable of making this happen which is why I'm chipping in on this one.  So I'm backing two horses in this race And yes, I'm up for making my bounty pledge official on Buntysource or wherever

Thanks thoughtfan.  I updated the bounty post to show the new total of 2.35 BTC.  I suspect there might be some more pledges, and then perhaps we could move the pledged funds to a multisig 2-of-3 address controlled by 3 trusted members of the forum.  Refund TXs could be issued instantly for all pledges using N_LOCKTIME where N_LOCKTIME defines the deadline for winning the bounty. 

I should also point out that the bounty (at least as I specified it) did not require any particular coin to be cloned--just that the clone had to achieve sufficient adoption as evident by the number and magnitude of claims that were made and as evident by the spin-off trading on an exchange.  I suppose we could revisit the exact requirements to claim the bounty if more people are interested in contributing. 

Thanks for the proposal and clarification Peter.  I prefer a multisig means of pledging with a time limit and am happy to go with that.  I did understand and to confirm, yes I am happy with the 'any spin-off' criterion, in that it may well be something other than Aetherium.

[DeathAndTaxes]

Additional thoughts

Hashing the claim entries into a Merkle tree and requiring the claimant to provide the Merkle-branch proof increases the size of the blockchain should a large number of claims be made; however, the big benefit is that this seems to simplify the cloning process.  It means that the clones don't need to be aware of or manage snapshot.bin.  They just need to define a new type of claim TX that verifies the signature (either using FCV or SCV) and then follows the Merkle branch down to its root and compare that to the hard-coded Merkle root.  If the signature verifies and the Merkle branch leads to the hard-coded root hash, and if the claim has not already been made, then the claim TX is valid.

It is an interesting idea and probably worth the savings in the genesis block.  If the merkle tree is constructed based on the full claimset then the same tree could be used for more than one spinoff even if they have different criteria (i.e. spinoff A excludes dust claims below 1 bit, spinoff B excludes P2SH claims) as the merkle tree is a super set of all valid claims.  Websites could be created to show potential users what claims they have on multiple spinoffs.  Obviously after some time passes a new snapshot should be taken but multiple spinoffs could use the same snapshot and gain some economies of scale.

But will it be more difficult for the clones to verify that a particular claim hasn't already been made using this method?

The simplest method would be for full nodes to maintain an ordered list of claimed claims.

So validation becomes:
1) Is Claim improperly formatted has parsing error or is otherwise invalid (doesn't meets spinoff claim requirements)?  If so then stop, invalid because not a valid claim.
2) Is Claim authenticated (will vary depending on FCV or SCV)? If not then stop, invalid claim due to invalid signature/txn.
3) Is ClaimId in the claimed list?  If so then stop, invalid because already claimed (a double claim attempt).
4) Is Claim Merkle Branch invalid for the Claim Merkle Root Hash?  Is so then stop, forged claim or misconstructed merkle branch.

[Peter R]

Sorry that I haven't been active in the development.  This is more for "fun" and the development which pays the bills has been taking up most of my time.  

This is a "fun" project for me too.  I do think we are making good progress, however.

To expand on Peter's "to merkle or not to merkle" discussion
1) Peter, a merkle branch only need one hash per level not two (the other side is computed each level from the claim txn) and a single bit to indicate if the additional hash is on the left or right).  You also don't need to include the root hash for the same reason.  If that doesn't make sense I can go into detail but I will wait to avoid a long explanation on what might just be a simple oversight.  The size of a merkle branch (in bytes) for up to 32 levels would be: branch_size = (merkle_levels * digest_size)+4.

Yes, of course.  I've never coded a Merkle tree or used a Merkle branch so I missed the obvious fact that the other side follows from the claim TX.  What you just said makes perfect sense.  

3) A smaller hash digest (100 to 128 bit) could be used but that only provides a minimal reduction in size.  The set is fixed so it can be guaranteed to be collision free.  A preimage attack against even a 100 bit reduced length hash is infeasible at the current time.  It may however make sense to benchmark the speed of various hash functions as there will be a large number of branch validation in bootstrapping nodes.   I know off the top of my head SHA-512 has much higher throughput than SHA-256 on most systems this is due to SHA-512 using 64 bit words.  NIST does rate SHA-2 to be used in "cutdown" digests (i.e. take left 128 bits) and there are no known security implications in doing so.

Good point.  There's no need to use 256-bit hashes, so we can save space this way like you said.  

It is an interesting idea and probably worth the savings in the genesis block.  If the merkle tree is constructed based on the full claimset then the same tree could be used for more than one spinoff even if they have different criteria (i.e. spinoff A excludes dust claims below 1 bit, spinoff B excludes P2SH claims) as the merkle tree is a super set of all valid claims.  Websites could be created to show potential users what claims they have on multiple spinoffs.  Obviously after some time passes a new snapshot should be taken but multiple spinoffs could use the same snapshot and gain some economies of scale.

I am leaning towards the Merkle tree approach.  Let's see if anyone has any valid objections.  

But will it be more difficult for the clones to verify that a particular claim hasn't already been made using this method?

The simplest method would be for full nodes to maintain an ordered list of claimed claims.

So validation becomes:
1) Is Claim improperly formatted has parsing error or is otherwise invalid (doesn't meets spinoff claim requirements)?  If so then stop, invalid because not a valid claim.
2) Is Claim authenticated (will vary depending on FCV or SCV)? If not then stop, invalid claim due to invalid signature/txn.
3) Is ClaimId in the claimed list?  If so then stop, invalid because already claimed (a double claim attempt).
4) Is Claim Merkle Branch invalid for the Claim Merkle Root Hash?  Is so then stop, forged claim or misconstructed merkle branch.

Yes, that's what I was thinking too.  It does mean that the spin-off developer needs to include code to manage the ordered list of claimed claims (an additional requirement) but I think this is still easier than managing the full snapshot.bin file.