Pages:
Author

Topic: Spin-offs: bootstrap an altcoin with a btc-blockchain-based initial distribution - page 7. (Read 53604 times)

full member
Activity: 209
Merit: 100
Stellar is unfortunately not a pure spin off and BTC claims will be available "real soon now or in 6 months or so".

Somebody will eventually do a pure Spin-off of Ripple tho ...
member
Activity: 72
Merit: 10
Looks like Stellar is distributing some of their coins as a Bitcoin spin off.

https://www.stellar.org/about/mandate/#Bitcoin_program



Clam, lottoshares, and stellar are all using this idea. It's catching on.
legendary
Activity: 2968
Merit: 1198
Looks like Stellar is distributing some of their coins as a Bitcoin spin off.

https://www.stellar.org/about/mandate/#Bitcoin_program

full member
Activity: 209
Merit: 100
It also simplies the genesis block requirement for spin-offs: only the MerkleRoot is needed (along with the bitcoin blockhash for SCV).  I think this should be the recommended manner in which a spin-off verifies a claim, even though it increases the blockchain size if a large number of claims are eventually made.    

If a claim can reference an earlier claim you can avoid duplicating internal hashes. A valid proof need only reach a hash previously proven to have a path to the root.


Very nice, potentially a huge optimization
legendary
Activity: 2968
Merit: 1198
It also simplies the genesis block requirement for spin-offs: only the MerkleRoot is needed (along with the bitcoin blockhash for SCV).  I think this should be the recommended manner in which a spin-off verifies a claim, even though it increases the blockchain size if a large number of claims are eventually made.    

If a claim can reference an earlier claim you can avoid duplicating internal hashes. A valid proof need only reach a hash previously proven to have a path to the root.
legendary
Activity: 1162
Merit: 1007
One recommendation would be to remove the section_ids (as the records are self describing) and instead add a value (in bytes) to the header with the offset to the first record of each type.

For example in your sample the offsets would be
0x01 = 4800000000
0x02 = 9F00000000
0x03 = BC00000000
0x04 = 2A01000000

Agreed.  This makes the body of the file a contiguous list of claims but still allows for fast searching. 

Here is a good native multisig (vout:2) to use in your example instead of a fake one 14015bd586c0c7a28979ca294b114441f23bfc97be17cd6077b9e12e2709fec3:2.

Thanks.  I'll update the example files when I make the other updates and after people have had a chance to comment. 

By the way, do you think my requirement that the claims in snapshot.bin are sorted is overkill?  I did it for two reasons: (1) to permit efficient searching, and (2) as part of making the snapshot file a deterministic output of the block number. 

Also, the more I think about Smooth's suggestion to provide a Merkle-branch as part of the claim TX, the more I like it.  It means that as long as one trusts that the Merkle root in the genesis block corresponds to that from a legitimate snapshot, he can verify any particular claim TX with just the TX itself (without looking anything up in snapshot.bin).  The method seems more transparent, as it puts the onus on the claimant to provide proof (which gets mined when he is awarded his spinoff).  It also simplies the genesis block requirement for spin-offs: only the MerkleRoot is needed (along with the bitcoin blockhash for SCV).  I think this should be the recommended manner in which a spin-off verifies a claim, even though it increases the blockchain size if a large number of claims are eventually made.   


newbie
Activity: 43
Merit: 0
donator
Activity: 1218
Merit: 1079
Gerald Davis
Here is a good native multisig (vout:2) to use in your example instead of a fake one 14015bd586c0c7a28979ca294b114441f23bfc97be17cd6077b9e12e2709fec3:2.
https://blockchain.info/tx/14015bd586c0c7a28979ca294b114441f23bfc97be17cd6077b9e12e2709fec3

It uses an uncompressed pubkey (which would use the 0x05 prefix in the compact PubKey format).

Code:
type:     03
m:        01
n:        03
pubkey_1: 05e6da9c60084b43d28266243c636bcdaf4d8f17b5954e078d2dece7d4659e0dee
pubkey_2: 0226cb0561011d9045f6371cb09086ba7148d9942328bcf1dd78cb6edb35ccdda9
pubkey_3: 022eac137ab02d826df0af54e92a352945c9892df6cd77f1a7c390fc82c8b0edea
value:    e02e00000000

hex:      03010305e6da9c60084b43d28266243c636bcdaf4d8f17b5954e078d2dece7d4659e0dee0226cb0561011d9045f6371cb09086ba7148d9942328bcf1dd78cb6edb35ccdda9022eac137ab02d826df0af54e92a352945c9892df6cd77f1a7c390fc82c8b0edeae02e00000000

hash:     e41ce373c2e37bf853242c5ac0775af56e0f54f9
legendary
Activity: 2198
Merit: 1014
Franko is Freedom
donator
Activity: 1218
Merit: 1079
Gerald Davis
Nice diagrams. I love it when a plan comes together.

One recommendation would be to remove the section_ids (as the records are self describing) and instead add a value (in bytes) to the header with the offset to the first record of each type.

For example in your sample the offsets would be
0x01 = 4800000000
0x02 = 9F00000000
0x03 = BC00000000
0x04 = 2A01000000

Alternatively you could include a claim_type record for each type just after the header and before the array of claims which has the type, offset, count, value, size but that might be overkill.  The last option would be to not include the section size or section header (i.e. header then list of claims much like a block is a header and list of txns).  The snapshot will probably be parsed to a database (at least key value db like leveldb) for processing anyways.
legendary
Activity: 1162
Merit: 1007
Example Snapshot.bin File

To clarify and cement the format for snapshot.bin, I've prepared a very simple example file below.  Although it includes only 6 claim entries, it should be complete.  I prepared this file manually, so it is certainly possible that it contains errors.  The updated file format spec can be found here.




In case anyone is interested in checking my Merkle root calculation, here are the hex-encoded claims:

Code:
claim1: 016260d83d6028f8c92a9ea3f723e1f5035248b6341027000000000000
claim2: 018f0e683058da332f749e8a8a14927b4ed62281983075000000000000
claim3: 01efd640847b6af5cc93708229de90032e23d5c7c2204e000000000000
claim4: 0245b6221f874ca90e020115d4b6c6ee09b4ca9865409c000000000000
claim5: 03010305e6da9c60084b43d28266243c636bcdaf4d8f17b5954e078d2dece7d4659e0dee0226cb0561011d9045f6371cb09086ba7148d9942328bcf1dd78cb6edb35ccdda9022eac137ab02d826df0af54e92a352945c9892df6cd77f1a7c390fc82c8b0edeae02e000000000000
claim6: 04360076a914d4ecfa2ca508e5fe44b2a9273580c9a938e07f5f887c76a914e82bb22fd5d0c7e84d9bf135e6de8017110e717088527b7b52ae1027000000000000

The claims all correspond to valid unspent balances as of Block #312,580.  Here are the details:

Code:
claim1: 19yBEgoGAEEsw5sFGMGCQpKi4uL4RLVmPV
claim2: 1E3QtSv491Ku8EH3jN3hBErzQnm3YpSoPv
claim3: 1Ns9ALf53Do1dLQs2o1UyZTFnt9JGGKRTP
claim4: 383cjd6WpW9AZrA9Rw7h6MPMUsDzLihxMu
claim5: 14015bd586c0c7a28979ca294b114441f23bfc97be17cd6077b9e12e2709fec3:2
claim6: 66747648ef92d78bb36c267c0f444e6df96e44f463a2f92541483fcb8e882b27:1



How to Construct the Merkle Tree

The image below shows the Merkle Tree construction for the example snapshot.bin file prepared above.  



The row of leave hashes was constructed by hashing the claim entries sequentially in the order they appear in snapshot.bin.

Code:
MT[1,1] = hash(claim 1)
MT[1,2] = hash(claim 2)
MT[1,3] = hash(claim 3)
MT[1,4] = hash(claim 4)
MT[1,5] = hash(claim 5)
MT[1,6] = hash(claim 6)

The second row was constructed by hashing the concatenation of the adjacent hash values.  Because this resulted in an odd number of hashes, the last hash was duplicated:

Code:
MT[2,1] = hash(MT[1,1]   concat   MT[1,2])
MT[2,2] = hash(MT[1,3]   concat   MT[1,4])
MT[2,3] = hash(MT[1,5]   concat   MT[1,6])
MT[2,4] = MT[2,3]

This procedure was repeated to build the third row:

Code:
MT[3,1] = hash(MT[2,1]   concat   MT[2,2])
MT[3,2] = hash(MT[2,3]   concat   MT[2,4])

And finally we arrive at the Merkle root:

Code:
MerkleRoot = MT[4,1] = hash(MT[3,1]   concat   MT[3,2])

For snapshot.bin, the hash function is RIPEMD160:

Code:
hash(x) = ripemd160(x)


Well, there goes my Saturday morning Smiley  Time to go out and enjoy the afternoon sun.  



===========================================
REVISIONS

03-Aug-14:
 - Updated example file and Merkle tree diagram as per recent changes to snapshot.bin format (remove section markers) and by replacing the fictitious claim 5 with a real one.  

full member
Activity: 209
Merit: 100
you got 1 BTC from me

Awesome!  Thanks cypherdoc. 

This brings us to 3.35 BTC of pledges so far ($2010).  I think next week we can discuss setting up a multi-sig address to formalize this, but for now let's just review the requirements for claiming the bounty.  It's important to be as clear and unambiguous as possible.

Quote
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 thread1.

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. 

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


I think it's implied that the spin-off must work.  I believe I've covered this because it would be difficult to achieve 1% claims by value and by count if the spin-off was fundamentally broken (and hopefully it would never make it onto an exchange if that were the case).

The requirement that 1% of the claims must be claimed doesn't sound like a lot, but it would mean that 15,000 - 30,000 claimants (not necessarily unique individuals) controlling at least 130,000 BTC have taken action related to the spin-off.  So 1% claimed claims would seem to imply significant interest. 

The requirement that 99.9% of the wealth being claimable probably needs to be clarified.  As of Block 305,303, only 99.84% of the wealth could be refactored as P2PkH.  But there's probably been just enough inflation since this block to push this to 99.85% which rounds to 99.9% (unless more wealth has moved to P2SH addresses).  Since we are right on the edge here, should we stick to 99.9% or make a definitive decision about spin-offs that only support type=01 (P2PkH) claims?


Perhaps an additional requirement is that the developer must not abandon the spinoff or "retire from development" but rather continue tracking the commits in the underlying forked system at least until some well defined time in the future such that other developer(s) come forward and are ready to assume the maintainer position with push-level privileges to the github repo to continue tracking the original system (i.e. Aethereum tracking Ethereum). 

I heard rumors that there are now tools to auto-merge commits from the parent repo into a fork assuming no conflicts arise and automated test suites still complete with success.

P.S. I'm doubling my pledge to 2 BTC.

Cheers ...
legendary
Activity: 1162
Merit: 1007
Length bytes
With a fixed size value field for all records the length of 0x01 and 0x02 records will always be 29 bytes so no length field is needed.


For 0x03 the length can be computed from the "n" value (length = 11+ n*33)
...

Yes, that's what I've done in both cases.  The only claim-type where I encode the length directly is for the rawScript-type claims.  

I do encode the byte length of each claim section immediately before the list of claims (for that section). But this just happens once per section (so four times in total).  This is useful if you want to skip immediately to the P2SH section, for instance.  
legendary
Activity: 1162
Merit: 1007
you got 1 BTC from me

Awesome!  Thanks cypherdoc.  

This brings us to 3.35 BTC of pledges so far ($2010).  I think next week we can discuss setting up a multi-sig address to formalize this, but for now let's just review the requirements for claiming the bounty.  It's important to be as clear and unambiguous as possible.

Quote
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 thread1.

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.  

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


I think it's implied that the spin-off must work.  I believe I've covered this because it would be difficult to achieve 1% claims by value and by count if the spin-off was fundamentally broken (and hopefully it would never make it onto an exchange if that were the case).

The requirement that 1% of the claims must be claimed doesn't sound like a lot, but it would mean that 15,000 - 30,000 claimants (not necessarily unique individuals) controlling at least 130,000 BTC have taken action related to the spin-off.  So 1% claimed claims would seem to imply significant interest.  

The requirement that 99.9% of the wealth being claimable probably needs to be clarified.  As of Block 305,303, only 99.84% of the wealth could be refactored as P2PkH.  But there's probably been just enough inflation since this block to push this to 99.85% which rounds to 99.9% (unless more wealth has moved to P2SH addresses).  Since we are right on the edge here, should we stick to 99.9% or make a definitive decision about spin-offs that only support type=01 (P2PkH) claims?
legendary
Activity: 1162
Merit: 1007
Example of Uncompressed PubKey -> PubKeyHash
http://webbtc.com/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098

PubKey: 0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d 4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee
PubKeyHash ( HASH-160): 119b098e2e980a229e139a9ed01a469e518e6f26
The Address: 12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX


Example of Compressed PubKey -> PubKeyHash
http://webbtc.com/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098

PubKey: 024d57123256b2a84e6618bc12b08f81cd54ec79fcd7a55a129eee9402bac8d5f7
PubKeyHash ( HASH-160): f4f5209eb5bce683a4a1dd325e22bdda6a31cf95
Address: 1PLDXZPhFEfGGxdXr54FxvWUvWcRCrjHEG


I agree now.  I had convinced myself there was some ambiguity somewhere but there's not.  The pubkeys will be in some format (compressed or uncompressed) and we simply hash whatever that is.  Zero ambiguity.  

legendary
Activity: 2968
Merit: 1198
Needing to trust the exchange "will do the right thing with the coins" is 100% opposite to pushing forward a new future of trustless transacting

It's not trusting them to do the "right" thing, it is about deciding as a customer what exchanges you want to use. It is possible for example that exchanges consider spun-off coins are part of their fee structure and write that into the agreement. As a customer you get to decide whether you want to pay that fee or take your business (or at least your idle coins) elsewhere.

I agree that if there is nothing in the agreement "legally" the spun off coins probably belong to the customer but frankly I doubt this is going to be a useful approach. Many exchanges will simply not have any feasible mechanism for distributing the spin-offs (particularly when the value of the spin off is less than the cost of processing), so if pressed legally they will perhaps pay damages once (if that; infeasibility may be a valid defense) and then change their agreements.

The practical remedies available to the customers are: 1) withdraw your coins, perhaps temporarily, before the ex date; or 2) shop around for an exchange that does distribute spin-offs. The latter might happen by holding customer coins using segregated private keys and then allowing the customer to retrieve those keys, but I doubt any exchange is implemented that way now.

donator
Activity: 1218
Merit: 1079
Gerald Davis
Regarding compressed vs uncompressed pubkeys, I think perhaps there are some subtleties whenever a pubkey gets refactored as P2PkH.  Like we were discussing in the Sigsafe thread, there are two addresses for each 256-bit privkey depending on whether the compressed or uncompressed key gets hashed.  So, I guess we need to standardize on which one we select when we're required to make a choice.  I would propose to always hash the compressed pubkey.  

We just use exactly whatever the user used in the output.  So if they have an uncompressed pubkey we take the hash of the uncompressed pubkey.  

Sadly most wallets aren't smart enough to realize that if the user has a private key he has both the uncompressed and compressed pubkey and thus could sign using either one.  If the user has a privatekey marked internally as uncompressed he won't see the compressed address in his wallet and if he tries to sign for that address he will get an error.  Technically the user could still claim it by exporting his uncompressed private keys and reimporting them as compressed private keys but that wouldn't be very user friendly.  So we use what the user used.

Example of Uncompressed PubKey -> PubKeyHash
http://webbtc.com/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098

PubKey: 0496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52da7589379515d 4e0a604f8141781e62294721166bf621e73a82cbf2342c858ee
PubKeyHash ( HASH-160): 119b098e2e980a229e139a9ed01a469e518e6f26
The Address: 12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX


Example of Compressed PubKey -> PubKeyHash
http://webbtc.com/tx/0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098

PubKey: 024d57123256b2a84e6618bc12b08f81cd54ec79fcd7a55a129eee9402bac8d5f7
PubKeyHash ( HASH-160): f4f5209eb5bce683a4a1dd325e22bdda6a31cf95
Address: 1PLDXZPhFEfGGxdXr54FxvWUvWcRCrjHEG


We aren't changing uncompressed to compressed or compressed to uncompressed just hashing the key as provided to produce the PubKeyHash.  In the first example the user has address 12c6DSiU4Rq3P4ZxziKxzrL5LmMBrzjrJX in his wallet.  If we switched that pubkey to a compressed pubkey 0296b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52 and hashed it we would end up with address 1PKW9GWX2P2JhCSR17BXa4B8MJ4ozUjW9Y which is probably not in his wallet (although he has the required private key).



legendary
Activity: 1764
Merit: 1002
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 Smiley And yes, I'm up for making my bounty pledge official on Buntysource or wherever Smiley

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. 

you got 1 BTC from me
legendary
Activity: 1162
Merit: 1007
I think that is mostly it.  

Regarding compressed vs uncompressed pubkeys, I think perhaps there are some subtleties whenever a pubkey gets refactored as P2PkH.  Like we were discussing in the Sigsafe thread, there are two addresses for each 256-bit privkey depending on whether the compressed or uncompressed key gets hashed.  So, I guess we need to standardize on which one we select when we're required to make a choice.  I would propose to always hash the compressed pubkey.  

Quote
Claim Values
On edit: I saw your note on more efficient searching by having static record size after writing this.  I could have swore when I read it before it said varint but maybe I was just seeing things.

It said varInt for about an hour (until I realized the issue).  I'm thinking of making the two varInts in the header uint64_t now too, just for simplicity.  

Quote
Merkle Tree
You should be explicit in indicating how the txn are ordered (I would assume the same order as the file) for creating the merkle tree.  Also explicitly indicate how to handle an odd number of claims.  One claim will need to be hashed to itself first or last is equally good but it should be defined.

Yes, I will make this explicit shortly (I'm going to follow the format used when hashing the transactions in a bitcoin block exactly, except for the hash function).  Bitcoin uses sha256 twice (I suppose to guard against length extension attacks) so perhaps we should do the same.  Can you recommend a hash function to use?  I proposed ripemd160 (hash160).  
donator
Activity: 1218
Merit: 1079
Gerald Davis
Snapshot.bin File Format V0.3

...

So, I'm thinking this does everything.  But it almost seems too simple (I think I'm missing some details regarding compressed vs. uncompressed pubkeys).  I'm sure someone will find some more mistakes or improvements Smiley

I think that is mostly it.  

Claim Values
On edit: I saw your note on more efficient searching by having static record size after writing this.  I could have swore when I read it before it said varint but maybe I was just seeing things.  Lookup time is probably something to consider.  I guess it may makes sense to use unit_64 in the serialization.  As long as the hashes are computed the same way they can be stored internally as the developer sees fit.  The key thing is for the serialized claim that is to be hashed having a single specific form and simple is probably better.   I will leave the notes below as they may be used internally by a developer to compact the snapshot.bin.

The exact varint being used should be clarified since the hashes for the claims (ClaimId?) and the merkle tree will depend on the exact serialization of the bytes.  In Bitcoin what is commonly referred to as "varint" is called "compact_size" in the source code.  Bitcoin also uses a true varint internally which is more space efficient (not sure why Satoshi felt the need for two formats).   The "internal varint" is base-128 and is a better fit here.  More info: http://en.wikipedia.org/wiki/Variable-length_quantity.  Most bitcoin (or cryptocurrency) libraries should have support for base-128 (although it may be named differently).

A weighted average of all claims results in an average value field size of:
uint_64 - 8 bytes per record
bitcoin "compact size" - 3.91 bytes per record (51% space reduction)
varint (base-128) - 2.85 bytes per record (64% space reduction)

PubKeys In Native Multisig
I would recommend storing all PubKeys (native multisig) in compact form.  This is an internal form used by bitcoind for reducing the size of the UTXO and shouldn't be confused with compressed keys.  In compact form all pubkeys are stored as 33 bytes in the form of .  The y values are not stored and are reconstructed as needed.

Compact PubKey prefixes
0x02 = Compressed Key (even)
0x03 = Compressed PubKey (odd)
0x04 = Uncompressed PubKey (even)
0x05 = Uncompressed PubKey (odd)

Length bytes[/b]
With a fixed size value field for all records the length of 0x01 and 0x02 records will always be 29 bytes so no length field is needed.


For 0x03 the length can be computed from the "n" value (length = 11+ n*33)
...

This would allow you to save 1 byte per record (except the very few unclassified scripts).


Merkle Tree
You should be explicit in indicating how the txn are ordered (I would assume the same order as the file) for creating the merkle tree.  Also explicitly indicate how to handle an odd number of claims.  One claim will need to be hashed to itself first or last is equally good but it should be defined.
Pages:
Jump to: