Topic: Spin-offs: bootstrap an altcoin with a btc-blockchain-based initial distribution - page 8. (Read 53604 times)
July 25, 2014, 11:50:27 AM
Just a note about the V0.3 proposed file format for snapshot.bin: I used uint64_t (8 bytes) to encode the value, rather than varInt, because it allows for (easier) O(log n) searching of (sorted) claims within the type=0x01 and type=0x02 sections of the file (the longest sections). This is also why I added the section marker bytes (faster searching).
July 25, 2014, 11:43:35 AM
So then it will probably be a low chance of receiving coins from an exchange that haven't yet been claimed. So this will allow exchanges to check every coin in their inventory and claim for the ones that have not yet been claimed and that to me is a very grey area because essentially its their inventory.
I think a good corollary would be merge mining and transaction fees in pool mining. Initially some pools kept the merged mining coins and transactions fees. Competition by pools which paid those out forced most pools to adopt similar policies.
There is no decentralized protocol that could be used to force exchanges to "payout" the spinoff coins. It will simply require competition and education. If enough users demand it and are willing to switch exchanges they will be forced to give users that capability. Especially among exchanges which trade altcoins this can be a very powerful low cost way for the exchange to gain volume (and thus fees) in a spinoff coin. Instantly all their BTC depositors are also xyzCoin depositors as well. Many will probably immediately trade either "cashing out" to BTC or scooping up the spinoff at a low cost.
As for the spinoff being "gray area" I don't think it is. The relationship between an exchange (or wallet or other third party crypto service) and users is one of bailor and bailee. It is the user's property it is just under the custody of the exchange operator. Saying it is a gray area would be like saying if your broker took the dividends of your stock it would be a gray area because the stock is in an account at the brokerage. Granted no such legal cases have occurred (yet) but I can't see a court agreeing that an exchange is entitled to the benefits of its users property.
Quote
To me this proves to be a slight problem being that the exchanges will then have most of the bootstrapped coins.
That is probably not true. The rate that claimants make their claims is unknown however the exchanges do not have the majority of the Bitcoins in circulation and thus they wouldn't have the majority of the valid claims either. The largest known bailors (google it) of Bitcoins are BitStamp and Second Market with about 3% and 1% of the outstanding BTC. In the case of BitStamp since they made their cold storage addresses known (so called "audit") it would be impossible for them to claim the property of their users without it being public knowledge.Still if you are worried start asking exchanges what their policy would be on spinoff claims from the user's coins in their custody.
July 25, 2014, 11:14:35 AM
I've seen this thread from the start but not so much the middle, so I wanted to double-check:
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
That depends on the account agreement between the customer and the exchange. I suspect the answer to #2 is "No" initially and "Yes" if this method becomes commonplace. One reason to try to standardize it is to facilitate exchange support.
For the time being customers can temporarily withdraw their coins from an exchange across the ex date if they want to (be able to) claim their coins.
So then it will probably be a low chance of receiving coins from an exchange that haven't yet been claimed. So this will allow exchanges to check every coin in their inventory and claim for the ones that have not yet been claimed and that to me is a very grey area because essentially its their inventory. To me this proves to be a slight problem being that the exchanges will then have most of the bootstrapped coins. And many more complications with it
I believe the core attributes will still be a huge boon for coins being able to leverage bitcoin but i also see it giving exchanges even more power and it negates some of the fair distribution plights. That is kind of what we should be aiming to remove almost completely one day and not the other way around. and of course this is also the issue for mining pools and any other medium!
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
July 25, 2014, 03:38:54 AM
I've seen this thread from the start but not so much the middle, so I wanted to double-check:
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
That depends on the account agreement between the customer and the exchange. I suspect the answer to #2 is "No" initially and "Yes" if this method becomes commonplace. One reason to try to standardize it is to facilitate exchange support.
For the time being customers can temporarily withdraw their coins from an exchange across the ex date if they want to (be able to) claim their coins.
July 25, 2014, 03:33:01 AM
I've seen this thread from the start but not so much the middle, so I wanted to double-check:
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
1. places like exchanges would end up with spinoff coins?
2. If so, would the user owning the account on the exchange, be able to get/access the spinoff coins?
I think the answer is 1. Yes. 2. No
July 24, 2014, 05:21:42 PM
Snapshot.bin File Format V0.3
This post represents the third revision to the snapshot.bin file format specification proposal. The following file format encodes 100% of the spendable bitcoin wealth. Spin-off developers are free to support claims of only a subset of this total.
Snapshot.bin File Structure
Spin-off developers would likely include only the Merkle root and blockhash in the spin-off's genesis block if they chose to use Smooth's proposal, but are free to include the entire file.
Although outside the scope of snapshot.bin, spin-off developers should also include the Bitcoin blockhash when the spin-off goes live (to act as a time-stamp to avoid pre-mine accusations) and other implementation-dependent genesis block data as required (e.g., a pubkey to prove that you are the developer in order to allow you to claim the spin-off bounty).
Claim Entries
Claim types
All claim entries begin with a type-identifier byte. The format of each entry depends on the value of this type-identifier byte. There are four possible claim entry types.
When constructing the snapshot file, pay2PubKey claims, 1-of-1 multisig, and multisig claims where only 1 pubkey is valid (and only 1 is required) shall be refactored as P2PkH claims. Unspent outputs claimable by the same claimer shall be combined into a single claim. Unspendable claims shall be removed.
Format for Type 0x01 (P2PkH) claim entries
99.84% of the valid unspent outputs are either P2PkH or can be recast as P2PkH claim entries. These claims shall be encoded in the following format:
Format for Type 0x02 (P2SH) claim entries
0.16% of valid unspent outputs are P2SH type that shall be encoded in snapshot.bin in the following format:
Format for Type 0x03 (Native multisig M-of-N) claim entries
0.0001% of the unspent outputs are native multisig (that cannot be refactor as type 0x01). These claims shall be encoded in the following format, where the list of pubkeys is sorted canonically from smallest to largest (the byte at the greatest offset in memory is considered most significant for sorting purposes):
All pubKeys in the native multisig section shall be encoded 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)
Format for Type 0x04 (raw script) claim entries
0.0000% (16 entries as of Block #305,303) cannot be easily refactored into one of the three previous formats, and shall thus be recorded verbatim as raw script:
Sorting claim entries into snapshot.bin
The claim entries are sorted by type, where the P2PkH (type=0x01) section comes first, and the RawScript (type=0x04) section comes last. The file header specifies the byte offset to each claim section.
Within each section, the claim entries are also sorted canonically to permit faster searching.
P2PkH-section: sorted by pubKeyHash from smallest to largest. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
P2SH-section: sorted by scriptHash from smallest to largest. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
NativeMultisig-section: Each claim entry in this section is hashed with RIPEMD-160. The claims are written to snapshot.bin in order of increasing hash value. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
RawScript-section: Each claim entry in this section is hashed with RIPEMD-160. The claims are written to snapshot.bin in order of increasing hash value. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
Snapshot.bin's Merkel Tree
The claim entries are hashed into a Merkle tree in the same manner as the transactions in a bitcoin block are hashed into a Merkle tree. Hash160 is used instead of sha256d to reduce the size of the Merkle branches used when claiming one's share of spin-off.
An example of how the Merkle Tree for Snapshot.bin is constructed is given here.
Endianness and uints
All unsigned integers are serialized using the little-endian convention.
When sorting hash values canonically, the byte at greatest offset in memory is assumed most significant (little-endian convention).
===========================================
REVISIONS
26-Jul-14:
- Removed all varInts in favour of fixed-width integers.
- Clarified the manner in which claim entries are sorted.
- Added the note written by DeathAndTaxes regarding the pubkey format.
- Clarified endianness details.
- Posted example snapshot.bin file and Merkle tree construction here: https://bitcointalksearch.org/topic/m.8040377
03-Aug-14:
- Removed section markers in favor of section byte offset specified in header.
This post represents the third revision to the snapshot.bin file format specification proposal. The following file format encodes 100% of the spendable bitcoin wealth. Spin-off developers are free to support claims of only a subset of this total.
Snapshot.bin File Structure
Code:
Field Description Size
================================================================================================
Version 01 00 00 00 4 bytes (uint32)
MerkleRoot Merkle root of claim entries (hash160) 20 bytes
Blockhash hash of Bitcoin block that snapshot was taken from 32 bytes
TotalClaimValue the sum of all the claims (in satoshis) 8 bytes (uint64)
NumClaims the number of claims to follow 8 bytes (uint64)
P2PkHOffset the file offset in bytes for P2PkH claim section 8 bytes (uint64)
P2SHOffset the file offset in bytes for P2SH claim section 8 bytes (uint64)
NatMultisigOffset the file offset in bytes for native multisig claim section 8 bytes (uint64)
RawScriptOffset the file offset in bytes for raw script claim section 8 bytes (uint64)
ClaimEntries the list of claims (sorted)number of claims
Spin-off developers would likely include only the Merkle root and blockhash in the spin-off's genesis block if they chose to use Smooth's proposal, but are free to include the entire file.
Although outside the scope of snapshot.bin, spin-off developers should also include the Bitcoin blockhash when the spin-off goes live (to act as a time-stamp to avoid pre-mine accusations) and other implementation-dependent genesis block data as required (e.g., a pubkey to prove that you are the developer in order to allow you to claim the spin-off bounty).
Claim Entries
Claim types
All claim entries begin with a type-identifier byte. The format of each entry depends on the value of this type-identifier byte. There are four possible claim entry types.
Code:
Type Description
=======================
0x01 P2PkH
0x02 P2SH
0x03 Native multisig
0x04 Raw script
When constructing the snapshot file, pay2PubKey claims, 1-of-1 multisig, and multisig claims where only 1 pubkey is valid (and only 1 is required) shall be refactored as P2PkH claims. Unspent outputs claimable by the same claimer shall be combined into a single claim. Unspendable claims shall be removed.
Format for Type 0x01 (P2PkH) claim entries
99.84% of the valid unspent outputs are either P2PkH or can be recast as P2PkH claim entries. These claims shall be encoded in the following format:
Code:
0x01
Format for Type 0x02 (P2SH) claim entries
0.16% of valid unspent outputs are P2SH type that shall be encoded in snapshot.bin in the following format:
Code:
0x02
Format for Type 0x03 (Native multisig M-of-N) claim entries
0.0001% of the unspent outputs are native multisig (that cannot be refactor as type 0x01). These claims shall be encoded in the following format, where the list of pubkeys is sorted canonically from smallest to largest (the byte at the greatest offset in memory is considered most significant for sorting purposes):
Code:
0x03…
All pubKeys in the native multisig section shall be encoded 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
Compact PubKey prefixes
0x02 = Compressed Key (even)
0x03 = Compressed PubKey (odd)
0x04 = Uncompressed PubKey (even)
0x05 = Uncompressed PubKey (odd)
Format for Type 0x04 (raw script) claim entries
0.0000% (16 entries as of Block #305,303) cannot be easily refactored into one of the three previous formats, and shall thus be recorded verbatim as raw script:
Code:
0x04
Sorting claim entries into snapshot.bin
The claim entries are sorted by type, where the P2PkH (type=0x01) section comes first, and the RawScript (type=0x04) section comes last. The file header specifies the byte offset to each claim section.
Code:
… // type 0x01 claims … // type 0x02 claims … // type 0x03 claims … // type 0x04 claims
Within each section, the claim entries are also sorted canonically to permit faster searching.
P2PkH-section: sorted by pubKeyHash from smallest to largest. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
P2SH-section: sorted by scriptHash from smallest to largest. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
NativeMultisig-section: Each claim entry in this section is hashed with RIPEMD-160. The claims are written to snapshot.bin in order of increasing hash value. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
RawScript-section: Each claim entry in this section is hashed with RIPEMD-160. The claims are written to snapshot.bin in order of increasing hash value. It is assumed that the byte at the greatest offset in the hash value is the most significant (little endian convention).
Snapshot.bin's Merkel Tree
The claim entries are hashed into a Merkle tree in the same manner as the transactions in a bitcoin block are hashed into a Merkle tree. Hash160 is used instead of sha256d to reduce the size of the Merkle branches used when claiming one's share of spin-off.
An example of how the Merkle Tree for Snapshot.bin is constructed is given here.
Endianness and uints
All unsigned integers are serialized using the little-endian convention.
When sorting hash values canonically, the byte at greatest offset in memory is assumed most significant (little-endian convention).
===========================================
REVISIONS
26-Jul-14:
- Removed all varInts in favour of fixed-width integers.
- Clarified the manner in which claim entries are sorted.
- Added the note written by DeathAndTaxes regarding the pubkey format.
- Clarified endianness details.
- Posted example snapshot.bin file and Merkle tree construction here: https://bitcointalksearch.org/topic/m.8040377
03-Aug-14:
- Removed section markers in favor of section byte offset specified in header.
July 24, 2014, 12:42:25 PM
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.
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.
Quote
Quote
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.
July 24, 2014, 12:27:17 PM
Quote
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.
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.
Quote
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.
July 24, 2014, 12:21:56 PM
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.
July 24, 2014, 12:13:37 PM
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.
July 24, 2014, 12:10:44 PM
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.
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.
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.
July 24, 2014, 11:53:36 AM
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 July 24, 2014, 11:18:38 AM
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:
The number of rows in the Merkle tree is given by:
1 + ceiling (log2 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?
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 (log2 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?
July 24, 2014, 03:37:39 AM
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
Also provides proper reference points for the appropriate reward / effort ratio given other similar C++ projects
July 24, 2014, 02:31:47 AM
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.
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.
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.
July 24, 2014, 01:55:29 AM
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.
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.
July 24, 2014, 01:36:13 AM
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.
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.
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.
July 23, 2014, 06:11:14 PM
I am joining this bounty with 1 BTC
Awesome. I've updated my post above.
July 23, 2014, 04:46:45 PM
I am joining this bounty with 1 BTC
July 23, 2014, 03:06:29 PM
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 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 the final details regarding the snapshot.bin file format can be coordinated.
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 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 the final details regarding the snapshot.bin file format can be coordinated.
Jump to: