Transaction Tree

Atomic batched state updates. Roughly analogous to the blocks committed to a blockchain

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

JavaScript

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 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() see the genAccount() and use of circomlibjs's eddsa prv2pub.

Solidity

As is shown in Layer 2 Withdrawals to Layer 1, a user's withdrawal on L1 begins as follows:

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 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, MiMC7 is used. 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 and the Circom circomlib poseidon component are capable of handling 8 inputs in a single hash.

Zero Knowledge

The 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.

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

JavaScript

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:

.
.
.
// 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);
.
.
.

Solidity

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

L2 State Update

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

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() method aforementioned in the Account/ State Tree section on account trees in Solidity.

Zero Knowledge

In update_state_verifier.circom , 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 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];
    }
}