Quote from: Jeff Jefferson on April 16, 2014, 03:57:42 PM

Quote from: paspi on April 15, 2014, 11:56:59 PM

Android wallet update 2:

Hey paspi, amazing news!

I've read your post a couple of times now. And still I don't fully understand the way the wallet works or the possible problem. Roll Eyes

Maybe you could explain it using an example? I'm not that techy so please keep it simple. I would really like to help you.

Oh, OK.

Normally, reference client works by validating the blockchain from block #0 to block #250,000. The ledger is public, every POW or POS block generated (and the transactions in them) are public, and the reference client just fetches them from the network, and replays it. It also stores every block and every transaction, so it can cope with the network choosing one branch over another.

Each block (POS or POW) has a difficulty target contained in it, the block's information can be used to prove that CPU time was spent there and block is indeed at least as difficult as it claims to be. Soemtimes main chain can fork, and reference clients follow the chain with the largest amount of work in it. But they can switch over to another branch if network chooses to continue on it and its total amount of work (since block #0) passes the others.

On the other hand, SPV clients are light weight they don't store every block or every transaction. They just store last 5000 blocks' headers (amount of CPU work in the block, and block's connection to older blocks up to genesis can be verified from there). They try to keep track of every possible branch by its cumulative work (since block #0), and follow the longest one. They don't try to verify any transactions, just show the user received coins if they notice a transaction to their own addresses. Verification means the coins you received were spendable by the person who sent them to you (1.the coins was really received by his address previously, 2. and they were not spent before).

This spent/unspent verification can continue up to Block #0 in a reference client. A SPV client trusts that this verification was made by the network, and network won't relay invalid blocks to the SPV client. Even if a rogue peer sends some blocks that look legitimate by their Proof Of Work, but don't contain valid transactions; eventually cpu power of network would gain advantage and would generate more Proof Of Work (resulting in a longer chain), surpassing rogue peer's chain.

For a theoretical SPV client for POW+POS coins, last paragraph is what causes the problem. The amount of work specified in a block's header is indeed correct, and can be summed up to the genesis block to see which chain has more work in it. But if the block is not POW but a POS block, work amount specified in block header is very low, the actual difficulty exists in the coinstake transaction.

If a client does not verify coinstake transactions, a rogue party can just feed him lots of POS blocks with invalid transactions in it, faster than what the network generates. Client will believe the longer chain is the correct chain, and follow it; it may end up in a fraudalent payment that looks as received on SPV client.

All clients keep track of spent and unspent transactions only on the main chain. If another chain is found out to be longer, all blocks on the old chain from the fork point is disconnected, and blocks on the better chain are connected one by one. While connecting blocks one by one, transaction verification is done on every new block. This is a reorganization, happens once in a while when some parts of the network follow different blocks, but sorts itself out after some transactions (it's the reason for 50 confirmation limit).

The second problem for a SPV POW+POS client lies in the above paragraph. A SPV POW+POS client might say "I will only store last 5000 blocks and transactions, and I will use them verify transactions when reorganization occurs. And leave the rest of the transactions unverified if I don't have information on their source coins anymore"). Now here's the attack: because I know that client verifies transactions only in the main chain, and does not try to verify transactions on other chains until they become longer than the main chain, I can feed the client a total of 5000 blocks in multiple chain branches to overwrite the valid blocks in its storage (but without any of the branch becoming longer than the main chain), then once I know the client doesn't store historical blocks, I can make one of by chains longer than the main chain, and lure the client.

To overcome this problem, not only light-verification of the longest chain is needed, but all chains must be verified to prevent them becoming longer than main chain earlier if there are already problems with them. (This verification is challenging part). Also all transactions need to be stored for those stored blocks (because any of them may be needed to verify a further POS block), this is another problem.

For POS blocks that cannot be verified (and also cannot be marked as invalid, block seems legit but client deleted its history so it cannot verify it anymore) ; I decided on counting their difficulty in the chain as zero (instead of their target difficulty), so if a long series of unverifable POS blocks won't be able to cause that chain to become longer. The network will have the advantage if it can generate *verifiable* blocks faster than the attacker.

These measures are necessary for being sure that you actually received the incoming transactions and that you are not scammed.

Quote

Do you see any possibility of a malfunction or a possible scam when the android wallet you're developing uses only the transactions of the last 40 days?

Is this problem only relevant for the minting process or is it necessary to have the whole blockchain on the android device in order to simply send and receive mintcoins?

Maybe it is possible to verify only some blocks of the blockchain instead of having the whole blockchain on the android device. I mean additionally to the blocks from the last 40 days maybe only verify the 100th or the 10000th block of the blockchain. That way it is secured that the correct blockchain is used? Or is it another problem?

Also maybe it is possible to mint using the android device without securing the network? (<-sound stupid but i mean it). As long as enough wallets are run on the laptops and pcs the network is secure.

Thank you for your efforts and your explanations!

Actually I'm thinking on this. Probably minted POS blocks on android will not include broadcasted transactions as they cannot actually prove the transactions are valid (It won't be good to include non verifiable transactions in a block, the network would reject the block and all work to generate that POS block will be wasted). Although this would mean android wallets would be selfish, not helping to include transactions in the blockchain, it also means that they won't receive the transaction fees, leaving them to other clients to collect. So I guess it's fair.

Sorry for the long post. The subject has too many delicate details and I guess in the end I will have to write a whitepaper on it to describe it properly with all the issues.