Mình tự xây một Simple Scalable Solution cho Ethereum - phần 2

Protocol

1. Deposit và giao dịch trên Layer 2

• User A deposit tiền vào Layer 1, một event sẽ phát ra

• Layer 2 lắng nghe event deposit trên Layer 1 và gửi từ tài khoản của operator vào cho user A số tiền tương ứng.

• User A thực hiện giao dịch trên Layer 2

2. Update user state và state proof

• Định kỳ qua thời gian T, operator của Layer 2 sẽ bundle toàn bộ transaction mới nhất để tính state proof(*) chính là merkle root của các transaction đó.

• Operator update lên Layer 1 các thành phần sau:

  • Tất cả state (balance) mới nhất của tất cả các user

  • Số tiền mỗi user đã claim ngược ra từ Layer 2 ở period này

  • State proof vừa mới tính được ở bước trên

3. Rút tiền từ Layer 2 về Layer 1

• User A muốn rút tiền từ Layer 2 về Layer 1 thì gửi ngược tiền vào tài khoản của operator

• Chờ đến định kỳ T khi operator thực hiện bundle transactions, user A có thể tính claim proof(**) cho các claim transactions rồi mang lên Layer 1 để rút tiền.

• Layer 1 verify claim proof và release tiền cho user A.

Proofs

State proof (*)

State proof chính là merkle root của merkle tree được tạo nên bởi tất cả các transaction ở bundle period hiện tại. Sau khi bundle, các transaction này sẽ được đánh dấu để tránh bị bundle ở period sau. Thuật toán để tạo merkle root từ một danh sách các transactions có thể dùng cấu trúc dữ liệu queue đơn giản như sau:

Pseudo code:

 build (transactions) {
        if (transactions.length == 0) return null;      
        // turn all transactions into tree nodes (content, left, right)
        // consider this nodes a queue data structure
        const nodes = transactions.map(tx => new {
            content: hash(tx), 
            left: null, 
            right: null
        });
        // build tree
        while (nodes.length > 1) {
            // dequeue 2 elements
            const left = nodes.shift();
            const right = nodes.shift();
            const newNode = { 
                content: hash(left.content + right.content), 
                left: left, 
                right: right
            };
            // push into the queue
            nodes.push(newNode);
        }

        // root node
        return nodes[0];
    }

Claim proof (**)

Claim proof của mỗi user chính là các transaction mà user này gửi vào tài khoản của operator trong period đó cùng với bằng chứng merkle path đi theo. Vấn đề là nếu có nhiều transaction, thì mỗi transaction lại cần một merkle path gây lãng phí không cần thiết. Chúng ta có thể chỉ cần dùng 1 merkle path cho toàn bộ các transaction cần được verify.

Như hình trên, giả sử cần xác thực các giao dịch là nút a,c,d,g,m (nút màu hồng), ta chỉ cần merkle path là các màu xanh dương b,ef, h, ijkl, n, op là đủ để xây dựng lại merkle root.

Để làm được việc này, chúng ta cần giải quyết 2 việc:

• Tạo combined merkle path cho multiple transactions

• Verify a batch of transactions với chỉ một merkle path

Thuật toán để tạo Merkle path cho multiple transactions khá đơn giản. Ý tưởng là:

• Dùng một tập hợp path để chứa các node sẽ được thêm vào merkle path.

• Vẫn dùng queue Q để chứa các transaction cần được build merkle path.

• Lần lượt duyệt toàn bộ các phần tử trong Q. Nếu sibling chưa có giá trị, ta bổ sung giá trị ấy vào trong path, rồi tính node cha p và đưa vào Q

Bạn có thể tham khảo code mình dưới đây để rõ hơn:

getCombinedMerklePath(leaves) {
        const path = [];
        const checked = [];
        const queue = [...leaves];
        while (queue.length > 0) {
            const node = queue.shift();
            checked.push(node);
            if (node.parent != null) {  
                if (node.parent.left.hashValue == node.hashValue) {
                    // check if right node is already in the queue, if not add it to the path
                    if (queue.findIndex(n => n.hashValue == node.parent.right.hashValue) == -1) {
                        // check if right node is checked, if not add it to the path
                        if (checked.findIndex(n => n.hashValue == node.parent.right.hashValue) == -1) {
                            path.push(node.parent.right);
                        }
                    }
                } else {
                    // check if left node is already in the queue, if not add it to the path
                    if (queue.findIndex(n => n.hashValue == node.parent.left.hashValue) == -1) {
                        // check if left node is already in the path, if not add it to the path
                        if (checked.findIndex(n => n.hashValue == node.parent.left.hashValue) == -1) {
                            path.push(node.parent.left);
                        }
                    }
                }

                // check if parent is already in the queue, if not add it to the path
                if (queue.findIndex(n => n.hashValue == node.parent.hashValue) == -1) {
                    queue.push(node.parent);
                }
            }
        }
        return path;
    }

Tiếp theo, mình cần verify bao gồm một danh sách các transaction và một danh sách các node trong merkle path. Vấn đề là mình không biết sẽ nên combine thế nào với nhau để tạo merkle root. Điều này dẫn tới việc chúng ta phải đánh index cho toàn bộ các node để từ đó mới có manh mối rebuild lại merkle root.

Cách đánh index cho các node cũng đơn giản. Xuất phát từ root, ta đánh id là ‘0’. Với mỗi node bất kỳ, ta đánh id của 2 node con bên ấy bằng cách lấy id của node đó nối với ‘0‘ nếu là node trái, là ‘1’ nếu là node phải. Như vậy, node B trên hình vẽ sẽ có id là ‘00001‘, node IJKL sẽ có id là ‘010’.

index() {
        this.root.id = '0';
        let queue = [this.root];        
        while (queue.length > 0) {
            const node = queue.shift();
            if (node.left != null) {
                node.left.id = node.id + '0';
                queue.push(node.left);
                node.right.id = node.id + '1';
                queue.push(node.right);
            }
        }
    }

Cuối cùng, mình có thể verify bundle dựa trên id của các node:

verifyBundle(leaves, path) {
        let allNodes = [...leaves, ...path];
        while (allNodes.length > 1) {
            // current node
            const curNode = allNodes.shift();
            // search for the sibling of the current node based on the current node's id
            const sibling = allNodes.find(n => n.id == curNode.id.slice(0, -1) + (curNode.id[curNode.id.length - 1] == '0' ? '1' : '0'));
            // if sibling is not found, return false
            if (sibling == undefined) {
                return false;
            }
            // calculate the parent node
            let parent = null;
            // if the current node is left node
            if (curNode.id[curNode.id.length - 1] == '0') {
                parent = new TreeNode(this.f.hash(curNode.hashValue + sibling.hashValue + ''), curNode.content + sibling.content, curNode, sibling);
            } else {
                parent = new TreeNode(this.f.hash(sibling.hashValue + curNode.hashValue + ''), sibling.content + curNode.content, sibling, curNode);
            }
            parent.id = curNode.id.slice(0, -1);
            // add parent node to the list of nodes
            allNodes.push(parent);                        
            //remove sibling node from the list of nodes
            allNodes = allNodes.filter(n => n.hashValue != sibling.hashValue);
        }
        return allNodes[0].hashValue == this.root.hashValue;
    }

Mình sẽ cố gắng viết demo và chia sẻ sớm nhất có thể!