Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)
No, you can get an upper bound on the size by the depth of the tree if you get the coinbase (or any other) txn, and a lower bound if you get given a transaction late in the block. You can get an exact measure by taking the rightmost branch and observing the duplicated hashes, but nothing more compact than that. Having a upper bound is probably good enough for me. The upper bound is the nearest power of 2, right? As a related question, in the current protocol, could an SPV node requests for the x-th transaction in the y-th block, without knowing the txid of the transaction? |
|
|
|
|
Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)
|
|
|
|
|
Example 2: the 4th output (sending to 17SEHdQNxrP64M6aUkDJtoUKAhSMujamhE) of 9abcc1383bcc5eb980dd263837c7bd368d0fd5d1696a89e49dc9e63c82e7ce16
The block has 460 transactions so 9 bits is needed for txindex
The tx has 21 outputs so 5 bits is needed to encode all outputs. However, with only 5 words and 20bits of checksum, only 3 bits is left. That means we could only encode the first 8 outputs.
version: 0
height: 0001010100011111100110 (346086)
txindex: 101111010 (378, or the 379th tx)
outputindex: 011 (3, or the 4th output)
information: 000010101-000111111-001101011-11010011
blockhash: 0x000000000000000000e83a55db617b5db59ce161f8ef4d0989b8c6d1a3e82102
scriptPubKey: 0x76a91446963eb29098f58519f94bd8c3130f5b5166123488ac
SHA256(blockhash-scriptPubKey) = 34e17a91bcccfb02b4eec27d035c3f5c2150675ede100d1be7549f2629b93a8a
Checksum = First 20 bits of SHA256 hash = 0011-0100-1110-0001-0111
With 2-bit checksum and 9-bit information for each word, it becomes:
00(c)
000010101(i)
11(c)
000111111(i)
01(c)
001101011(i)
00(c)
11010011(i)
111000010111(c)
So the 5 words address will be
00000010101-11000111111-01001101011-00110100111-11000010111
i.e. actor-side-estate-crunch-seed
|
|
|
|
Personally I think five words would be easy enough and if the checksum was spread across all five then that should help to prevent the five word sets from looking too similar to others that are from the same block.
In the example above I use 1 checksum + 10 information for each word. Maybe 2+9 is better to make the words look more "random" With 2-bit checksum and 9-bit information for each word, it becomes: 10(c) 000000000(i) 10(c) 000000000(i) 11(c) 0000000(i) 111011010010110100100101(c) So the 5 words address will be 10000000000-10000000000-11000000011-10110100101-10100100101 i.e. length-length-scatter-regret-pigeon |
|
|
|
I implemented it exactly as you proposed. https://github.com/NicolasDorier/NBitcoin/blob/master/NBitcoin/BrainAddress.csWe are already at 5 words though. (16 bit checksum) I also check, if there is unused bits, that they are all to 0. I still think 16 bits of checksum is overkill. If there is a mistake, the info should not be : out of the chain, out of the block, out of the transaction, but also encoded correctly. (correct number of bit for encoding transaction index and txout index) We need some independent security experts to suggest the appropriate number of checksum bits. Thanks for your coding but I can't read C. I'd like to illustrate with some examples: --------------------- The only output in the genesis block: version: 0 height: 0000000000000000000000 txindex: 0 outputindex: 0 information: 0000000000-0000000000-00000 blockhash: 0x000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f scriptPubKey: 0x4104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4 cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac SHA256(blockhash-scriptPubKey) = afb4b496b902df5adc89d9d89080f6dc80383dbe6e1067140721ed53e2ccbedb Checksum = First 30 bits* of SHA256 hash = 1010-1111-1011-0100-1011-0100-1001-01 With 1-bit checksum and 10-bit information for each word**, it becomes: 1(c) 0000000000(i) 0(c) 0000000000(i) 1(c) 00000(i) 011111011010010110100100101(c) So the 5 words address will be 10000000000-00000000000-10000001111-10110100101-10100100101 i.e. length-abandon-limit-regret-pigeon * I still assume minimum 20-bit checksum. It could be encoded in 4 words if 16-bit checksum is used. ** Since you are using 16-bit checksum instead of 20-bit as I suggest, there might not be enough checksum bits for each word if 4 checksum bits is used. So I'd like to standardize it to be 1+10 instead of 4+7 as I suggested before. |
|
|
|
Not trying to rip someone off here, recently had a situation where double spending saved the day.
My question is, what is the best way of double spending? (I have almost no clue what I'm talking about, please keep that in mind.)
Sending any amount without fees to 2nd address, then spend from 2nd address and resend from 1st address to a 3rd address with fee? (Would it then pick up the 0 fee transaction if transactions on 2nd address were made with fee (although input is still unconfirmed?))
Spending minimal amount without fees to 2nd address, where some additional coins gets sent back to yourself, which should make it minimal priority since it's so small, then send whole balance including the few unconfirmed ones that got sent back to yourself to 2nd address, then send new transaction with whole balance with fee to 3rd address?
I'm also thinking, if there's some reliable way to do this, maybe quite a few scams could be prevented by preemptively setting up a double spend scenario with a potential seller so that you have the option to chargeback if he turns out to be a scammer?
There is no "balance" in bitcoin protocol, only "unspent transaction output" (UTXO) |
|
|
|
|
It's essentially proof-of-stake. No matter how they call it it's proof-of-stake
|
|
|
|
It makes sense, the only thing I would fix is the size of the checksum to make it minimum 16, rounded up to fill the unused avalaible bits.
If we have 6 words but actually use 56 bits, then we can add 10 bits to the checksum.
Do you see a way of improving hardcoding the size of the block height ? 22 bits is only ok until block height of 4 million... I agree that we don't care right now, but if we find a nice way to increase without doing a new spec, it would be nice.
Actually I believe we will have some better way to encode before block 4M. It is also likely that there will be significant change in the blockchain structure and this scheme will obsolete. In such case, probably 21 bits is already enough as I expect such change would happen in 30 years. There is always a big temptation to reduce the number of checksum bits but each bit you cut halves the security. Wow, just now, the block 346019 has 2064 transactions. |
|
|
|
So a 5-words address would have
1 version bit
22 block height bits
1 to 11 txIndex bits
1 to 11 txOutputIndex bits
at least 20 checksum bits
To convert the bits into final address, we first serialize version-height-txIndex-txOutputIndex (the "information"). The information should be within 25-35 bits, and checksum is 20-30 bits To derive the first word, we take the first 4 bits from checksum and the first 7 bits from information. This is repeated until all information bits are included. The rest will be checksum if there is any left * A 6-words address would be encoded similarly, with 3 bits of checksum and 8 bits of information for each word. * I put checksum before the information to make each word looks more "random". Otherwise, some words would be used more frequently than others, especially the first 2 words which encodes the block height. |
|
|
|
I suspect I can fit some information about the block in the checksum.
I'm not sure if this is a right way to go. A checksum should be statistically independent from the information. Otherwise, it's not a checksum |
|
|
|
With 16 bit of checksum, it is possible to fit everything in 5 words.
Knowing the block, we know how much transaction there is, so we know how much bits to use for encoding.
Knowing the transaction, you know how much bits to use for encoding the TxOut index.
So if we take 24 bit for Block height (block 16 777 216), the transaction count is currently 10 bits, the TxOut index will be 1 bit most of the time. (OP_RETURN + Change)
So this gives us
24 + 10 + 1 + 16 = 51 bits for a 16 bit checksum, (5 words)
I would like to find a more efficient way of encoding the block though. (instead of hardcoding 24 bits)
good idea. This saves a lot. You certainly don't need 24 bits for block height. It takes >300years. All cryptography in current form should have been broken long before that. 22 bits (70 years) would be enough. The TxOut index is controlled by user so let's assume it to be usually 1 bit (because people want a short address) I want at least 20 bits of checksum (1 in a million error tolerance) I prefer to leave 1 version bit for future extension. (otherwise we may need to use a completely different word list for future encoding scheme) ----------------- So a 5-words address would have 1 version bit 22 block height bits 1 to 11 txIndex bits 1 to 11 txOutputIndex bits at least 20 checksum bits The txIndex and txOutputIndex will always use the least possible bits, leaving more room for the checksum. For example, if a block is known to have only 500 txs, the txIndex will only take 9 bits so the txOutputIndex may take at most 3 bits. If there is only 3 outputs (2 bits) in the tx, the checksum will have 21 bits EDIT: If there is not enough bits left to fully encode txOutputIndex, the earlier outputs are assumed. For example, if there are 14 outputs (4 bits) in the tx but only 2 bits is left for txOutputIndex, we could still encode the first 4 outputs with 5 words. Similarly, if a block has more than 2048 txs, a 5-words address is still valid if it is referring to first 2048 tx in the block and it is referring to the first or second output ------------------ If an address can't fit-in a 5-words address, it would need 6 words anyway. So a 6-words address would have 1 version bit 22 block height bits 1 to 22 txIndex bits 1 to 22 txOutputIndex bits at least 20 checksum bits 22 txIndex bits should be enough for a 800MB block. If that's still not enough, it could be extended to 7-words in a similar way. It is also valid to encode a 5-words address in 6-words, for extra checksum security. |
|
|
|
My proposal will insert bits derived from the block-hash everywhere in the address, so it is not possible to mine a vanity address without discarding a successful block. So your proposal of adding the blockhash in the checksum would do the trick for preventing vanity addresses ? And the checksum has to be broken down into pieces and inserted in every 11-bit block to make sure every word is pseudo-random. Vanity addresses are still possible, just by pure luck. No mining of vanity address is possible. I see your point with the checksum, I'll try to find a good way of encoding all of that. I came up with the 5 bit from the BIP39 checksum, but such checksum would be less used than a "brain address".
Encoding of private key and public key are different concepts. If you made a small mistake in private key, it is very likely to recover it by some burst force. If you sent you bitcoin to a wrong public key, it is totally irreversible. Case 1: Alice would like to transmit the private key "ABCD1234" to Bob. The private key has no checksum and is carrying 100BTC on the blockchain. However, due to unstable network, Bob received "ABBD1234". Bob will immediately find that the private key carries no bitcoin and will ask Alice to resubmit. Even if he can't reach Alice again, he can still try to burst force it with the available information. Case 2: Alice would like to transmit the public key "ABCD1234" to Bob. The public key has no checksum. However, due to unstable network, Bob received "ABBD1234". Bob sent 100BTC to "ABBD1234" and screwed up |
|
|
|
|
Let say 1% of the world population will exchange their bitcoin address once per day, which is 70,000,000/day
0.01% of them will make a random mistake. So there will be 7000 mistakes/day.
With 5-bits of checksum, there will be 218 irreversible erroneous transaction/day
With 16-bits of checksum, this reduce to once per day
With 21-bits of checksum, this reduce to once per 300 days
Satoshi uses a 32-bits checksum in bitcoin address. That becomes once per 1681 years
Having an address with only 4 words is great, but it gives a false sense of security. If we are going to establish an industry standard, I believe we have a moral responsibility to lay users. We all make mistakes, and I'm sure 0.01% is way underestimated.
(You may argue that a random mistake may just point to a non-existing output but I've already used conservative parameters in my estimation)
|
|
|
|
|
This is a bad analogy.
The correct one should be:
Bank = Bitcoin miner
Cheque = Bitcoin transaction
USD = Bitcoin
Bitcoin transaction, like a cheque, has no intrinsic value. But bitcoin transaction is not bitcoin
Buffett is an excellent investor but he doesn't invest in anything he doesn't understand. Obviously he doesn't understand Bitcoin at all.
|
|
|
|
Why won't they do that? Let say address of the block 987654 txindex 7777 output 888 is "best adult web". This address will be extremely valuable and all miners will try to grab it. Except the one that discover the vanity address also know the private key. Would you buy the key knowing someone you don't know own it ? Miners could sell the block space for the vanity address without knowing the private key. All they need to do is to put their client's transactions in the appropriate positions. If the incentive is big enough, strong miners may even try to orphan other people's block to grab a good address. My proposal will insert bits derived from the block-hash everywhere in the address, so it is not possible to mine a vanity address without discarding a successful block. Do you really think 5 bits of checksum is enough? An address with random error will have 3.125% of probability to be valid. It's just unacceptable especially for bitcoin which getting refund is totally impossible. I think it is enough, at the first place most words in BIP39 are hard to get wrong. But you might be right, I will play a bit with several way of encoding it, and see if I can find a compromise between size (which I would like max 4 words for now) and checksum. Right now, hhanh00 proposed something with more checksum, I hope finding something more space efficient though. This is not true. Please don't assume all people are native English speakers. Even for native speakers many words are still very similar gmaxwell has list some examples of poorly chosen words in BIP39: [choice, choose], [drip, script, trip], [risk, brisk], [load, road] some more: [awake, aware, away], [stamp, stand], [price, pride], [steak, stick] (frankly speaking, I can't differentiate between "steak" and "stick" at all) 5 bits is unacceptable. I think 16-bits is really minimum, with an error tolerance of 1/65536. 20-bits will give 1 in a million. Just use the blockhash as part of the checksum as I suggested. It's quite obvious. I can't add the 32 bytes, it would result in something nobody can remember. How much bit do you think should mitigate the problem enough ?Ok I understood what you meant, great idea. |
|
|
|
1. blockchain reorg This is the problem of the wallet implementation. Whether they are using my spec or not, they need to manage that correctly (needed for checking a Partial Merkel Tree), this is orthogonal to my spec. Do you refer to the fact that one "brain address" might point to an invalid TxOut after a reorg ? One way to mitigate that is to ask for 101 confirmations. (coinbase maturity) However, the fact that some services will not want waiting so much time, even if my spec ask for it, might be troublesome. I don't have a better solution though.Just use the blockhash as part of the checksum as I suggested. It's quite obvious. 2. Miners may try to fill up a block with garbage for a vanity address Why would they do that ? there is nothing to win by doing that. Why won't they do that? Let say address of the block 987654 txindex 7777 output 888 is "best adult web". This address will be extremely valuable and all miners will try to grab it. I will not use your encoding technique.
The reason is that there is no reason to choose the number of words in a "brain address". As opposed to a private key, the fewer the better.
The best way to encode a "Brain Address" is to use the VarInt encoding that all bitcoin wallet already implement. (or the less supported CompactVarInt internal to bitcoin core)
Also, encoding the TxIndex is inferior to encoding the PathToLeaf, for 2 reasons : it takes more space, and more than a simple Partial Merkle Tree would be required as proof. (whose proof checks are already implemented in all SPV wallets)
Code reuse would be maximized, code error minimized, so adoption by wallet providers should be better.
Moreover, each words represents 11 bits of information.
If we need 23 bit for encoding an address, then we have 10 bit that serve for nothing. I propose to fit the checksum inside.
The size of the checksum in bit would be something like Max(5, UnusedBitCount).
This should represent all current payment destination on 3 or 4 words. And it will goes up very very slowly.
[/quote] Do you really think 5 bits of checksum is enough? An address with random error will have 3.125% of probability to be valid. It's just unacceptable especially for bitcoin which getting refund is totally impossible. |
|
|
|
|
OP updated
I hope listing on OTCQX will bring some real liquidity to bitcoin market
|
|
|
|
I found a way to fix all the problems you pointed out.
Having a SPV proof
I will encode a location in the blockchain in the following way :
[Height]-[PathToLeaf]-[TxOut index] (I'll call such information a "blockchain address")
You have not fixed the following problems: 1. blockchain reorg 2. Miners may try to fill up a block with garbage for a vanity address To fix the reorg problem you have to include blockhash and/or tx-hash somewhere in your formula. This is tricky because that would lengthen the address To fix the vanity address problem miner shouldn't be able to determine the address before a block is found. Again, this is avoided if the blockhash is part of the formula ------------------------ I'd like to propose the following method for referring any ScriptPubKey on the blockchain. I don't care how people interpret the information in the ScriptPubKey: Version: 1 bit (always 0) Height: 20 bits (up to block 1048576, enough for 13 years) txIndex: 19 bits (up to 524288 tx/block, won't happen until the blocksize is >110MB) TxOut index: 8 bits (up to 256 outputs/tx) Checksum: 29 bits (slightly weaker than 32 bits in a standard bitcoin address) Total: 77 bits, requiring 7 words to encode All components are zero-padded. Anything beyond block 1048576 / txIndex 524288 / TxOut index 256 are invalid. Checksum is the first 29 bits of SHA256(Blockhash-ScriptPubKey) The 48-bits (Version-Height-txIndex-TxOut index) is split into 6 fragments of 8-bits The 29-bits Checksum is split into 5 fragments of 5-bits and 1 fragment of 4-bits Fragments are concatenated alternatively, so miners are not able to mine a vanity address without giving up a successful block hash. To resolve the address, an SPV node has to obtain the ScriptPubKey with Height-txIndex-TxOut index, and verify the Checksum with Blockhash-ScriptPubKey Reducing to 6 words is possible but it reduces the checksum security and future compatibility Version: 1 bit (always 0) Height: 20 bits (reducing to 19 bits will make it overflows in less than 4 years) txIndex: 16 bits (up to 65536 tx/block, won't happen until the blocksize is >13MB) TxOut index: 5 bits (up to 32 outputs/tx) Checksum: 24 bits (Not sure if this is enough) Total: 66 bits Or 5 words: Version: 1 bit (always 0) Height: 20 bits txIndex: 13 bits (up to 8192 tx/block, won't happen until the blocksize is >1.5MB) TxOut index: 4 bits (up to 16 outputs/tx) Checksum: 17 bits (This could be risky) Total: 55 bits 8 words would be good enough for foreseeable future. It's still much better than encoding an 160-bits address with 15 words: Version: 1 bit (always 0) Height: 22 bits (enough for >70 years) txIndex: 25 bits (enough for 6.8GB block) TxOut index: 11 bits (up to 2048 outputs/tx) Checksum: 29 bits Total: 88 bits |
|
|
|
FirstBits didn't require centralized trust. Indeed, I messed up with another service. By the way "1kk5k" is hardly memorizable, using words should be better. Would you memorize your bank account number? I won't. Why should I memorize by bitcoin address? |
|
|
|
|
Show Posts
