Thoughts about BTC CKB SPV client

BTC CKB SPV client.md

1. Instead of storing the MMR root (the hash of all current peaks), we can store an array of peaks (if there is not a peak at the position, value is null, otherwise value is merkle root of peak). This will reduce the amount of witness data required for updating the MMR and make it easier to prove values in it by scripts running on CKB. You can find (Solidity-ish) code for appending to the MMR here, and rolling it back in the Appendix. Access to all historical blocks seems important for unforseen use cases of the CKB BTC SPV client.

   1. An MMR is self describing, using the current height and index being proved, exactly which Merkle tree root in the array is needed for the proof can be discerned, as well as the L|R orientation of the hashes in the proof.

2. Only a block's transaction root hash is required for proving history, the MMR should be a list of transaction root hashes, this also reduces witness data needed for proofs. In the case of a re-org, the transaction root at the latest shared block between the forks will be the same and it will be committed to in the prevBlockHeader value in the first post-fork block.

3. Only 44 bytes per header of witness is required

   1. Difficulty target information can be cached in the cell, it will only change every 2 weeks, difficulty adjustments should be verified by CKB and the latest difficulty information should be stored in the cell. (less 4 witness bytes)
   2. Each block header contains a reference to the previous blockheader, which can be calculated by CKB during header verification. The latest block header hash committed to the MMR should be stored in the cell. (less 32 witness bytes)

4. Regarding cell contention: Bitcoin blocks are slow and it's unlikely there are different values being committed. It seems like only 1 cell should be needed and all users can reference it.

5. Regarding confirmations, it seems like the SPV client should be responsive and other scripts should specify their desired number of confirmations. This means that UX can be adjusted on a per-application basis while the SPV client remains robust. If desired the CKB BTC SPV client could be updated immediately after a block is mined.

   1. Any user should be able to call the re-org function, if a user can present an extension of the chain with x confirmations and a different transaction root at a specified position.
   2. Alternatively we could consider requiring for 6 confirmations on any header accepted by CKB. This would mean a delay in "jumping" assets, but moving assets across chains is similar to a bank wire operation. The block oracle could be delayed by ~1 hour and commit one block at a time, or ~2 hours and commit 6 blocks at a time (in both cases the latest 6 block confirmations would only be PoW verified and discarded, and only blocks with 6 confirmations would be added to the MMR). In this case the re-organization function is more only for emergencies.

   Appendix

   rollbackMMR(orphanedRoots[], proofLeaves[]) {
   		uint256 memory foundBit;
   		uint256 memory x=0;
   		uint256 memory y=0;
   		uint256 memory testInt
   		bytes32 memory testValue;
   		uint256 memory currHeight=CURRENT_HEIGHT; //height of current chain tip

   		for(x<orphanedRoots.length; x=0; x++;){ //rollback orphaned values 
   			foundBit=1
   			while (){//find lowest MMR peak 
   				testInt = currHeight >> foundBit //shift right to erase the bit if it is there
   				if(testValue << foundBit != currHeight){ // shift back left to correct, if information was lost there was a bit there
   					break
   				}
   				foundBit++
   			}
   			foundBit-- //correct for 0 to 1 used above
   	
   			//we've found the lowest peak, if height is odd, peak at this location contains the value to remove
   			if(currHeight%2=1){
   				require(peakArrayMemory[foundBit]=orphanedRoots[x])//ensure this is the correct value
   				peakArrayMemory[foundBit]=0;
   			} else {
   			//otherwise we need to walk up from the bottom of the peak (height is known from foundBit)
   				testValue=orphanedRoots[x]
   				for(z<foundBit; z=0; z++){//TODO: check for off by one
   					testValue=sha3(encodePacked(proofLeaves[y],testValue))//we refer to the last value in structure, always prove to the left
   					peakArrayMemory[z]=proofLeaves[y] //effects of removing the element
   					y++
   					}
   				require(peakArrayMemory[foundBit]=testValue);//ensure the proof was correct
   				}
   			currHeight--
   			}
   		}