# How to implement SPV of Arbitrum with Solidity

###### tags: `Public`

Author: celestialRiver

## 1. Antecedent Knowledge:

* Arbitrum is divided into *[Classic stack and Nitro stack](https://developer.offchainlabs.com/why-nitro#nitro-vs-classic)*, which can also be called system, hereinafter referred to as’ Classic’ and ‘Nitro’ respectively.
* Since August 31, 2022, no public arbitrum chain will continue to use the Arbitrum *[Classic](https://github.com/OffchainLabs/arbitrum)* stack, but the Arbitrum *[Nitro](https://github.com/OffchainLabs/nitro)* stack will be used instead
* *[Definition of Patricia Merkle Tree(MPT)](https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/)*

## 2. Life Cycle

### 2.1 Arbitrum Sequencer


Source: [*offchainlabs*](https://developer.offchainlabs.com/assets/images/seq-then-exec-0ec8fef09d47390cee2d6c2f7b5634d3.png)

### 2.2 TxHash

TxHash
=>
InboxMessageg
=>
SequencerMessage
=>
SequencerBatchItem
=>
SequencerFeedItem
=>
BroadcastFeedMessage
=>
BroadcastMessage
=>
SubmissionInputData

* In *SequencerBatchItem => SequencerFeedItem* part, Classic and Nitro both use **base64** format to process data.
* In *SequencerFeedItem => BroadcastFeedMessage* part, Nitro uses a general data compression algorithm called **brotli** to compress batches

---

## 3. Concrete Implementation

### 3.1 Procedures

1.TxHash => InputData => SubmissionInputData
//Prove that the InputData generated based on the TxHash submitted by the user is included in the SubmissionInputData provided by the local client

2.SubmissionInputData => SubmissionTxHashRLP => NewSubmissionTxHash
//Prove that the NewSubmissionTxHash generated by SubmissionTxHashRLP based on SubmissionInputData is consistent with the SubmissionTxHash submitted by the user

3.NewSubmissionTxHash + "MPT_proof" => L1Blockhash => Next
//Prove that the generated NewSubmissionTxHash is proved by MPT in combination with the block data and the L1Blockhash is passed to the next process

4.L1Blockhash + "OtherProof" => NowL1BlockHash
//Prove that L1Blockhash is a past block of NowL1BlockHash

### 3.2 Details

The user needs to provide TxHash and SubmissionTxHash.

***3.2.1 TxHash => InputData => SubmissionInputData***

***Purpose***: *To verify the validity of an L2 transaction in L1 transaction parameters.*

***Analysis***: *In view of the importance of this step, we need to analyze this step in detail.*

---

> **Classic**

The following proof methods are only applicable to ***Classic***, but they are also prerequisites for understanding ***Nitro***

* Suggest a transaction on Arbitrum: ***[0x6a1d](https://arbiscan.io/tx/0x6a1d569ca0a8a64d868092ed42ad7d194293c3059cf9780991174f43dd8d3ba5)***, record the hash as ***TxHash0x6a1d***
* Batches containing ***TxHash0x6a1d*** are packaged, compressed, and published to L1 by the Sequencer, and that hash is recorded as ***[SubmissionTxHash0xb150](https://etherscan.io/tx/0xb15092818da5384eb1e846dd1b1f4b92065cd1b71482867c456960a8c67367b2)***
* The ***InputData*** can be obtained through ***SubmissionTxHash0xb150***, which is recorded as ***SubmissionInputData0xb150***.
* The corresponding ***Transaction Info*** can be obtained through ***TxHash0x6a1d***, which is recorded as ***TxInfo0x6a1d***

// TxInfo0x6a1d
{
   hash: '0x6a1d569ca0a8a64d868092ed42ad7d194293c3059cf9780991174f43dd8d3ba5',
   type: 0,
   accessList: null,
   blockHash: '0x4dd97d8cbb5ef3e4fdddbc99ae813e8713f478902038dee8d1c672117ed35cfd',
   blockNumber: 17237171,
   transactionIndex: 0,
   confirmations: 22649108,
   from: '0xC0aF3690cCEdcc353AEb33cC0bB3eF63EF1070ba',
   gasPrice: BigNumber { _hex: '0x1c16ab5a', _isBigNumber: true },
   gasLimit: BigNumber { _hex: '0x079366', _isBigNumber: true },
   to: '0xC266551ef06b976AbC403F998Bd3Ae2398403937',
   value: BigNumber { _hex: '0x07911ad5a14714', _isBigNumber: true },
   nonce: 2,
   data: '0x',
   r: '0x8698fd9762461c6b042007e99a236d50f6cdaf5b6498e56832cbdfb470de6669',
   s: '0x6058d9801636a3f6c90db74b55c8dc611030715989a3b896e1fa66b30d8f2c9e',
   v: 84358,
   creates: null,
   chainId: 42161,
   wait: [Function (anonymous)]
}

* ***[L2Message data structure](https://github.com/OffchainLabs/arbitrum/blob/f565e0571b6883bd7021f926ba823e9d0b609b5f/packages/arb-evm/message/l2Message.go#L534)*** and ***Tx Info processing*** in Arbitrum:

txData := []interface{}{
  t.SequenceNum, //Nonce
  t.GasPrice,   //GasPrice
  t.GasLimit,   //GasLimit
  dest,      //To
  t.Payment,   //Value
  t.Calldata,   //Data
  v,       //V
  t.R,      //R
  t.S,      //S
 }

* [Handling **Nonce, GasPrice, GasLimit, To, Value, Data** from Tx Info:](https://github.com/OffchainLabs/arbitrum/blob/f565e0571b6883bd7021f926ba823e9d0b609b5f/packages/arb-evm/message/data.go#L245)

func encodeUnsignedTx(tx CompressedTx) ([]byte, error) {
    nonceData, err := rlp.EncodeToBytes(tx.SequenceNum)
    if err != nil {
        return nil, err
     }
    gasPriceData, err := rlp.EncodeToBytes(tx.GasPrice)
    if err != nil {
        return nil, err
    }
    gasLimitData, err := rlp.EncodeToBytes(tx.GasLimit)
    if err != nil {
        return nil, err
    }
    paymentData, err := encodeAmount(tx.Payment)
    if err != nil {
        return nil, err
    }

    var data []byte
    data = append(data, nonceData...)
    data = append(data, gasPriceData...)
    data = append(data, gasLimitData...)
    if tx.To == nil {
        data = append(data, 0x80)
    } else {
        destData, err := tx.To.Encode()
        if err != nil {
            return nil, err
        }
        data = append(data, destData...)
    }
    data = append(data, paymentData...)
    data = append(data, tx.Calldata...)
    return data, nil
}

* [Handling ***V,R,S*** from Tx Info:](https://github.com/OffchainLabs/arbitrum/blob/f565e0571b6883bd7021f926ba823e9d0b609b5f/packages/arb-evm/message/data.go#L245)

func encodeECDSASig(v byte, r, s *big.Int) []byte {
    data := make([]byte, 0, 65)
    data = append(data, ethmath.U256Bytes(new(big.Int).Set(r))...)
    data = append(data, ethmath.U256Bytes(new(big.Int).Set(s))...)
    data = append(data, v)
    return data
}

* By applying RLP(Recursive Length Prefix) to partial data of ***TxInfo0x6a1d*** and processing ***V, R, S***, we shall obtain the following data, noted as ***TxInfoRLP0x6a1d***

// TxInfoRLP0x6a1d
02841c16ab5a8307936694c266551ef06b976abc403f998bd3ae23984039378707911ad5a14714008698fd9762461c6b042007e99a236d50f6cdaf5b6498e56832cbdfb470de66696058d9801636a3f6c90db74b55c8dc611030715989a3b896e1fa66b30d8f2c9e

* Corresponding:

02 // SequenceNum/Nonce
84 // 0x84 - 0x80 = 4 bytes
1c16ab5a // GasPrice
83 // 0x83 - 0x80 = 3 bytes
079366 // GasLimit 
94 // 0x94 - 0x80 = 20 bytes
c266551ef06b976abc403f998bd3ae2398403937 // To
87 // 0x87 - 0x80 = 7 bytes
07911ad5a14714 // Value    
00 // V
8698fd9762461c6b042007e99a236d50f6cdaf5b6498e56832cbdfb470de6669 // R 
6058d9801636a3f6c90db74b55c8dc611030715989a3b896e1fa66b30d8f2c9e // S

* Find it in ***SubmissionInputData0xb150***:


* Hence, In ***Classic***, you can use ***TxHash*** to prove whether an L2 transaction exists in L1, that is, you can verify the validity of an L2 transaction in L1 transaction parameters.

---

> **Nitro**

* The life cycle of *Nitro* is basically the same as that of *Classic*, but in the process of ***SequencerFeedItem => BroadcastFeedMessage***, the ***brotli*** algorithm is used to compress the entire ***batch***. Because of this, the proof method applicable to Classic is not applicable to *Nitro*.
* Certification scheme applicable to Nitro (Scheme 3 is valid after testing):

1. Get ***SubmissionInputData0xb150***, deconstruct its data, get ***Batch*** data in it, and finally judge whether it contains ***TxInfoRLP0x6a1d***. (Failed)
2. Get all other ***txs*** in ***the same Batch block*** of ***Tx0x6a1d***, base64 all of them, and then assemble them into Batch data. Use ***brotli*** to compress them. Finally, compare the compressed data with ***SubmissionInputData0xb150***. (Failed)
3. Running an ***[Arbitrum Nitro Node](https://developer.offchainlabs.com/node-running/running-a-node)*** can directly synchronize the L1 status of each L2 transaction without proving through ‘Sequencer’ and other steps.

Arguments of Nitro:

* ***TxHash***: Transaction from Arbitrum. (User provided)
* ***SubmissionTxHash***: SubmissionTx on Ethereum L1. (User provided)
* ***SubmissionInputData***: InputData from SubmissionTxHash. (Local client)
* Run the ***[Arbitrum Nitro Node](https://developer.offchainlabs.com/node-running/running-a-node)*** off-chain, supply the ***TxHash*** provided by the user, and prove whether the ***TxHash*** is included in ***SubmissionInputData*** through the node data. If it is proven, go to the next step.

---

> Supplementary note — Assumption on verifying the effectiveness of TxHash:
> * We plan to add a new step to verify the effectiveness of **TxHash**. This step will be after Step 1 and before Step 2
> * Since the transaction **status** of TxHash on L1 exists in the **Arbitrum Nitro Node**, it can be assumed that it is based on the data provided by the Arbitrum Nitro Node.
> * Dropped the failed transactions, and build a Merkel tree off-chain by using the successful transaction hash. At the same time, build a Merkel tree on-chain. After the user provides **TxHash** and **proves** through the first step, verify the **MPT data** provided by the **TxHash** on-chain client. First, verify whether the **two Merkel trees** is consistent, and then verify whether **TxHash** exists in the Merkel tree.
>
> Question:
> 1. In what form is the transaction hash packed and compressed?
> 2. How often is it packed and compressed?
>
> Reference:
> [cirom and snarkjs](https://learnblockchain.cn/article/1078)

---

***3.1.2 SubmissionInputData => SubmissionTxHashRLP => NewSubmissionTxHash***

***Purpose**: To verify the validity of the submitted L1 transaction **parameter** that exists in the L1 transaction.*

***Arguments:***

* ***SubmissionTxHash***: from the last procedure
* ***SubmissionInputData***: from the last procedure
* ***SubmissionTxHashRLP***: RLP encode of SubmissionInputData

***Procedures:***

Upload ***SubmissionTxHash*** and ***SubmissionTxHashRLP*** on-chain for verification. Because ***SubmissionTxHashRLP*** contains ***SubmissionInputData***, ***Keccak256*** is used in the contract to calculate the hash of ***SubmissionTxHashRLP***, which is recorded as ***NewSubmissionTxHash***, and to verify whether ***NewSubmissionTxHash*** is consistent with ***SubmissionTxHash***. If it is consistent, the verification is passed.

//Solidity
function validateRLPTxInfoBySubTxHash(
        bytes memory rlpTxInfo,
        bytes[] memory header
    ) internal view;

---

***3.1.3 NewSubmissionTxHash + MPTproof => L1Blockhash => Next***

***Purpose**: To verify the validity of the submitted **L1 transaction** that exists in the **L1 Block**.*

***Arguments:***

* ***SubmissionTxHashRLP***: from the last procedure
* ***NewSubmissionTxHash***: from the last procedure
* ***L1BlockNumberMPTProof***: ***MPT*** data from SubmissionTx’s L1 Block
* ***L1BlockTxRootHash***: ***Root Hash*** from SubmissionTx’s L1 Block
* ***L1BlockHash***: ***Block Hash*** from SubmissionTx’s L1 Block

Upload five arguments on-chain for verification. The verification here is divided into four parts. If all four parts are passed, the verification is passed.

1. Verify the connection between ***SubmissionTxHashRLP*** and ***L1BlockNumberMPTProof***

// Solidity
function validateRLPTxInfoByProof(
        bytes memory rlpTxInfo,
        bytes[] memory proof
    ) internal view;

2. Verify ***L1BlockTxRootHash***

// Solidity
function validateTxRootHash(bytes[] memory proof, bytes[] memory header)
        internal
        view
        returns (bytes32 rootHash);

3. Verify ***L1BlockHash***

// Solidity
function validateBlockHash(bytes[] memory header) internal view;

4. Verify ***L1BlockNumberMPTProof***

// Solidity
function validateMPTProof(
        bytes32 rootHash,
        bytes memory mptKey,
        bytes[] memory proof
    ) internal view returns (bytes memory value);

---

***3.1.4 L1Blockhash + OtherProof => NowL1BlockHash***

***Purpose**: To verify the validity of the **L1 Block** that exists in the **L1 Blockchain**.*

***Arguments:***

* ***L1Blockhash***: from the last procedure
* ***L1BlockNumber***: corresponding block number
*
Here we are divided into two parts:

> **Off-chain:**

1. Get the block information from ***L1BlockNumber*** to ***the latest block number***, and sort them in order, 1.. 2.. 3… n.
2. Process the Raw Data of the second block to get the ***RLP*** code, and then use ***Keccak256*** to hash it to get the ***BlockHash*** of the second block.
3. Compare this ***off-chain BlockHash*** with the ***on-chain BlockHash***. If the same, the verification is passed.
4. Get ***ParentHash*** from the second block, and compare this to ***the first BlockHash***. If the same, the verification is passed.
5. Prove to the ***n-th*** block in turn.
6. It is required that the calculation time of the off-chain part is less than ***1h***, and if it exceeds ***1h***, it will continue to prove from the n-th block to the latest block number.
7. Arguments:
* ***ChainOffL1BlockHash***: BlockHash of the n-th block.
* ***ChainOffL1BlockNumber***: BlockNumber of the n-th block.

> ***On-chain:***

* Use ***blockhash (uint blockNumber)*** function in the contract to obtain the block hash with the block number of ***ChainOffL1BlockNumber***, which is recorded as ***NowL1BlockHash***.
* Compare ***NowL1BlockHash*** is equal to ***ChainOffL1BlockHash***. If the same, the verification is passed.

// Solidity
function validateBlockNumberhash(
     uint256 blockNumberPast,
     bytes32 blockHashPast
     ) internal view;

---

**3.1.5** The L2 transaction hash submitted by the user can be considered **valid** after the above **4** steps are proven.