# Transaction Tree

The *Account/ State Tree* section goes in depth on the operation of merkle trees; the concepts are the same here and will be presented in a more abridged format where appropriate. Further, the use of the transaction tree in withdrawals is detailed in depth in *Layer 2 Withdrawals to Layer 1*.

### Transaction Leaves

Transactions are the method of state update in RollupNC. Their application will be discussed in the later sections - for now, we care purely about their implementation within merkle trees. 

```
// pseudocode
type transaction = {
    from[2], // EdDSA pubkey of transaction sender
    fromIndex, // the index of the sender account in the state tree
    to[2], // EdDSA pubkey of the transaction recipient
    nonce, // the # of transactions the sender has made @ tx send time
    amount, // the number of (tokenType) tokens being sent in the tx
    tokenType // the id of the token being sent (TokenRegistry.sol)
}
```

<details>

<summary>JavaScript</summary>

Note: please see the *Solidity* expandable for an explanation on our implementation of a transaction hash.

You can see the generation of an arbitrary transaction leaf [as demonstrated in the BattleZips test file](https://github.com/BattleZips/RollupNC/blob/master/test/0.js#L206-L236) below:

```
const value = BigInt(20) // send 20 gwei
const tokenType = 1; // specify tx token as L1 gas token
const fromIndex = 2; // alice's account

.
.
.
const txData = [
    ...accounts.alice.L2.getPubkey(), // alice's eddsa pubkey
    fromIndex, // alice's eddsa pubkey
    ...accounts.bob.L2.getPubkey(), // bob's eddsa pubkey
    fromNonce, // nonce
    value, // tx token amount  (in tokenType)
    tokenType // tokenType (TokenRegistry.sol)
];
                
// compute tx leaf
const half = txData.length / 2; // verbose way of saying "4"
const leaf = poseidon([poseidon(txData.slice(0, half)), poseidon(txData.slice(half))]);
```

For more info on [`getPubkey()`](https://github.com/BattleZips/RollupNC/blob/master/test/utils/accounts.js#L121) see the [`genAccount()`](https://github.com/BattleZips/RollupNC/blob/master/test/utils/accounts.js#L73) and use of [circomlibjs's eddsa `prv2pub`](https://github.com/BattleZips/RollupNC/blob/master/test/utils/accounts.js#L49).

</details>

<details>

<summary>Solidity</summary>

As is shown in *Layer 2 Withdrawals to Layer 1*, [a user's withdrawal on L1 begins as follows](https://github.com/BattleZips/RollupNC/blob/master/contracts/RollupNC.sol#L187-L204):&#x20;

```
function withdraw(
    uint256[8] memory _tx, //[fromX, fromY, fromIndex, toX ,toY, nonce, amount, token_type_from, txRoot]
    uint256 _txRoot,
    uint256[] memory _txPosition,
    uint256[] memory _txProof,
    address payable _recipient,
    uint256[8] memory _proof
) public txTreeExists(_txRoot) {
    .
    .
    .
    // hash leaf
    uint256 leaf = PoseidonT3.poseidon([
        PoseidonT5.poseidon([_tx[0], _tx[1], _tx[2], _tx[3]]), 
        PoseidonT5.poseidon([_tx[4], _tx[5], _tx[6], _tx[7]])
    ]);
    // check for leaf withdrawl to prevent double spend
    require(!withdraws[leaf], "Tx already withdrawn");
    .
    .
    .
}
```

The [circomlibjs poseidon contract generator](https://github.com/iden3/circomlibjs/blob/main/src/poseidon_gencontract.js) is not capable of exposing a Poseidon function with 8 inputs. Therefore, for our updated exploratory version of this repository we hash half of each of the 8 inputs the hash the remaining two values together. This hash is a transaction leaf.

You may notice that there is no signature included in the transaction leaf. This is addressed both in *L2 Transacting* and *L2 Withdrawals to L1*. The mechanism of authorization of a transaction is separated from the mechanism of authenticating the integrity of a transaction.

Note that in the [original RollupNC repository](https://github.com/rollupnc/RollupNC/blob/master/contracts/RollupNC.sol#L194-L198), [MiMC7 is used](https://github.com/rollupnc/RollupNC/blob/master/contracts/helpers/MiMCMerkle.sol#L63-L70). It appears that this is actually more efficient than our implementation of Poseidon, likely due to the multiple hash function calls at a contract level required of the SnarkJS auto-generated solidity library.

Further note that this is the only limitation - the [JS circomlibjs poseidon library](https://github.com/iden3/circomlibjs/blob/main/src/poseidon_wasm.js) and the [Circom circomlib poseidon component](https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom) are capable of handling 8 inputs in a single hash.

</details>

<details>

<summary>Zero Knowledge</summary>

The [`tx_leaf.circom`](https://github.com/BattleZips/RollupNC/blob/master/zk/circuits/helpers/tx_leaf.circom) component is responsible for hashing transaction data into the leaf inserted into a transaction tree:

```
pragma circom 2.0.3;


include "../../../node_modules/circomlib/circuits/poseidon.circom";

template TxLeaf() {

    signal input from[2]; // Sender EdDSA pubkey [x, y]
    signal input fromIndex; // Sender index in balance tree
    signal input to[2]; // Receiver EdDSA pubkey [x, y]
    signal input nonce; // the sender's nonce for this tx
    signal input amount; // amount of tokens transfered
    signal input tokenType; // registry index for token type

    signal output out; // Transaction root to be used as merkle leaf

    component left = Poseidon(4);
    left.inputs[0] <== from[0];
    left.inputs[1] <== from[1];
    left.inputs[2] <== fromIndex;
    left.inputs[3] <== to[0];

    component right = Poseidon(4);
    right.inputs[0] <== to[1];
    right.inputs[1] <== nonce;
    right.inputs[2] <== amount;
    right.inputs[3] <== tokenType;
    
    component txLeaf = Poseidon(2);
    txLeaf.inputs[0] <== left.out;
    txLeaf.inputs[1] <== right.out;
    out <== txLeaf.out;
}

```

While the inputs are different, note that the mechanics/ function and outcome are very similar.

</details>

### Transaction Trees

Transaction trees are like blocks to the L2. Each state commitment that is not a deposit is committed on-chain. The ability to make a withdrawal or prove any action on the L2 is predicated on the inclusion of individual transactions in a transaction tree. Beyond this, there are no special tricks

<details>

<summary>JavaScript</summary>

The sequencer is tasked with the ingestion of proposed transactions into a transaction tree whose state transition is proven to be valid. Here we can see a (poorly optimized for readability) example of the process of [including a transaction into the tx tree](#transaction-leaves):

```
.
.
.
// see JavaScript Transaction Leaf Expandable for leaf construction        
const leaf = poseidon([poseidon(txData.slice(0, half)), poseidon(txData.slice(half))]);
const signature = accounts.alice.L2.sign(leaf);
txTree.insert(F.toObject(leaf));
                
    
// inputs used in the zk proof of state change between roots by tx tree
input.from.push(accounts.alice.L2.getPubkey());
input.to.push(accounts.bob.L2.getPubkey());
input.amount.push(value);
input.fromIndex.push(fromIndex);
input.fromNonce.push(fromNonce);
input.fromTokenType.push(tokenType);
.
.
.
```

</details>

<details>

<summary>Solidity</summary>

There are two points of contact for the Transaction tree with respect to the smart contracts:

#### [L2 State Update](https://github.com/BattleZips/RollupNC/blob/master/contracts/RollupNC.sol#L92-L110)

As will be expanded upon in *Layer 2 Transacting*, the main use of Zero Knowledge cryptography in RollupNC is to prove that the root of a transaction tree `t` applied to the root of a state tree `s` mutates the state tree root to `s'`. This ZK proof is shown below:

```
function updateState(
    uint256[8] memory _proof,
    uint256 _txRoot,
    uint256 _nextRoot
) public onlyCoordinator {
    // validate state change via zk proof
    uint256[2] memory a = [_proof[0], _proof[1]];
    uint256[2] memory b_0 = [_proof[2], _proof[3]];
    uint256[2] memory b_1 = [_proof[4], _proof[5]];
    uint256[2] memory c = [_proof[6], _proof[7]];
    uint256[3] memory input = [_txRoot, currentRoot, _nextRoot];
    require(usv.verifyProof(a, [b_0, b_1], c, input), "SNARK proof is invalid");
    
    // update merkle root
    uint256 prev = currentRoot;
    currentRoot = _nextRoot;
    updateNumber++;
    updates[_txRoot] = updateNumber; // <== stashes tx root for withdrawals
    emit UpdatedState(currentRoot, prev, _txRoot); //newRoot, txRoot, oldRoot
}
```

Note that, beyond the formal verification in Zero Knowledge of state transition integrity, there are no further uses of the transaction tree at this point. Instead, the operating parameters, including state and tree roots, are posted on-chain here.

#### [State Root Update](https://github.com/BattleZips/RollupNC/blob/master/contracts/RollupNC.sol#L195-L204)

As elaborated on in *Layer 2 Withdrawals to Layer 1*, in order to convince the RollupNC contract of your entitlement to some L2 tokens you must prove that a withdrawal transaction was committed to the Layer 1. By using a merkle proof of inclusion to demonstrate a withdrawal transaction's existence on L2, we have the tools for a reliable on-ramp/ off-ramp to provide circular movement on our L2 application.

```
.
.
.
// generate transaction leaf
uint256 leaf = PoseidonT3.poseidon([
    PoseidonT5.poseidon([_tx[0], _tx[1], _tx[2], _tx[3]]), 
    PoseidonT5.poseidon([_tx[4], _tx[5], _tx[6], _tx[7]])
]);
// ensure transaction leaf has not been nullified
require(!withdraws[leaf], "Tx already withdrawn");
//
require(
    _txRoot == getRootFromProof(leaf, _txPosition, _txProof),
    "tx does not exist in given transaction tree"
);
.
.
.
```

This relies on the [`getRootFromProof()`](https://github.com/BattleZips/RollupNC/blob/master/contracts/RollupNC.sol#L330-L341) method aforementioned in the *Account/ State Tree* section on account trees in Solidity.

</details>

<details>

<summary>Zero Knowledge</summary>

In [`update_state_verifier.circom`](https://github.com/BattleZips/RollupNC/blob/master/zk/circuits/update_state_verifier.circom#L66-L81) , each loop of verifies the inclusion of one transaction, then uses the parameters contained within that transaction to inform to computation of the next state root. This is shown more in *Layer 2 Transacting*.

[`tx_existence_check.circom`](https://github.com/BattleZips/RollupNC/blob/master/zk/circuits/helpers/tx_existence_check.circom) is the exact component used to prove the inclusion of a transaction leaf within a transaction tree (abridged without eddsa):

```
pragma circom 2.0.3;


include "./tx_leaf.circom";
include "./leaf_existence.circom";

template TxExistence(depth){

    /// SIGNALS IO ///

    // Transaction definition
    signal input from[2]; // Sender EdDSA pubkey [x, y]
    signal input fromIndex; // Sender index in balance tree
    signal input to[2]; // Receiver EdDSA pubkey [x, y]
    signal input nonce; // the sender's nonce for this tx
    signal input amount; // amount of tokens transfered
    signal input tokenType; // registry index for token type

    // Inclusion proof
    signal input root; // Transaction tree root
    signal input positions[depth]; // path to leaf being checked for inclusion
    signal input proof[depth]; // sibling nodes
    

    /// COMPONENTS ///
    component leaf = TxLeaf(); // compute tx leaf root from full tx leaf definition
    component leafExistence = LeafExistence(depth); // constraint by merkle inclusion proof

    /// CIRCUIT LOGIC ///

    // Compute tx leaf root
    leaf.from[0] <== from[0];
    leaf.from[1] <== from[1];
    leaf.fromIndex <== fromIndex;
    leaf.to[0] <== to[0];
    leaf.to[1] <== to[1];
    leaf.nonce <== nonce;
    leaf.amount <== amount;
    leaf.tokenType <== tokenType;

    // Confirm tx leaf root exists in tx tree root via merkle proof of inclusion
    leafExistence.leaf <== leaf.out;
    leafExistence.root <== root;
    for (var i = 0; i < depth; i++){
        leafExistence.positions[i] <== positions[i];
        leafExistence.proof[i] <== proof[i];
    }
}
```

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://battlezips.gitbook.io/battlezips/examples/rollupnc/transaction-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.