How to implement SPV of Arbitrum with Solidity

Orbiter_Finance

7 min readNov 30, 2022

Author: celestialRiver

1. Antecedent Knowledge:

Arbitrum is divided into Classic stack and Nitro stack, 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 stack, but the Arbitrum Nitro stack will be used instead
Definition of Patricia Merkle Tree(MPT)

2. Life Cycle

2.1 Arbitrum Sequencer

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.1.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, 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
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 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:

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:

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):

Get SubmissionInputData0xb150, deconstruct its data, get Batch data in it, and finally judge whether it contains TxInfoRLP0x6a1d. (Failed)
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)
Running an Arbitrum Nitro 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 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

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 + MPT_proof => 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.

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:

Get the block information from L1BlockNumber to the latest block number, and sort them in order, 1.. 2.. 3… n.
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.
Compare this off-chain BlockHash with the on-chain BlockHash. If the same, the verification is passed.
Get ParentHash from the second block, and compare this to the first BlockHash. If the same, the verification is passed.
Prove to the n-th block in turn.
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.
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.