Đề thi cuối kỳ môn CS251 (Tiền điện tử và Công nghệ Blockchain) năm 2021 của Đại học Stanford
Tuyển chọn TechFlowTuyển chọn TechFlow
Đề thi cuối kỳ môn CS251 (Tiền điện tử và Công nghệ Blockchain) năm 2021 của Đại học Stanford
Đề thi cuối kỳ môn CS251 (Tiền mã hóa và Công nghệ Blockchain) của Đại học Stanford năm 2021
Chuyên sâu báo cáo Web3Dịch bởi: Thực tập sinh TechFlow
Theo quy định rõ ràng và tinh thần của Quy tắc Danh dự Stanford, tôi không nhận được sự giúp đỡ nào cũng như không cung cấp sự giúp đỡ nào cho người khác trong kỳ thi này.
Chữ ký: _________________________
• Bài thi gồm 6 câu hỏi, tổng cộng 100 điểm.
• Bạn cần hoàn thành bài thi trong thời gian quy định.
• Làm bài trên Gradescope (D5GKRX).
• Trả lời ngắn gọn, súc tích.
Câu 1. (18 điểm) Câu hỏi vĩ mô.
A) → Hãy giải thích ngắn gọn tại sao các hệ thống Rollup lại lưu trữ mọi giao dịch trên chuỗi? Nếu dữ liệu giao dịch bị mất và không có bản sao lưu ở nơi nào khác thì điều gì sẽ xảy ra?
B) → Xem đoạn mã Solidity sau:
pragma solidity ^0.8.0;
contract ERC20 is IERC20 {
mapping(address => uint256) private _balances;
event Transfer(address indexed from, address indexed to, uint256 value); function _transfer(address sender, address recipient, uint256 amount) { emit Transfer(sender, recipient, amount);
}}
Giả sử mã này được triển khai trên hai hợp đồng: một hợp đồng tại địa chỉ X và một hợp đồng tại địa chỉ Y. Lựa chọn nào dưới đây có thể đọc được trạng thái _balances trong hợp đồng tại địa chỉ X? Khoanh tròn đáp án đúng (một hoặc nhiều).
A Mã trong hàm _transfer() tại địa chỉ X của hợp đồng ERC20
B Mã trong hàm _transfer() tại địa chỉ Y của hợp đồng ERC20
C Người dùng cuối sử dụng etherscan.io
C) → Tiếp nối câu hỏi trước, lựa chọn nào dưới đây có thể đọc được sự kiện phát ra Transfer khi hàm _transfer() được gọi? Vui lòng khoanh tròn đáp án đúng.
A Mã trong hàm getBalance() được định nghĩa tại địa chỉ X của hợp đồng ERC20
B Mã trong hàm getBalance() được định nghĩa tại địa chỉ Y của hợp đồng ERC20
C Người dùng cuối sử dụng etherscan.io
D) → Khi hai giao dịch Ethereum tx1 và tx2 được gửi đồng thời, giả sử maxPriorityFee của tx1 là y, maxPriorityFee của tx2 là 2y. Liệu tx2 chắc chắn được thực hiện trước tx1 trên chuỗi không? Hãy đưa ra câu trả lời và lập luận. Bạn có thể giả sử rằng maxFee của cả hai giao dịch đều lớn hơn baseFee + maxPriorityFee.
E) → Alice muốn mua một chiếc xe từ đại lý Bob. Cô ấy gửi 1 bitcoin đến địa chỉ Bitcoin của Bob. Bob chờ một giao dịch mà trong đó: 1) đầu vào đến từ địa chỉ của Alice, và 2) một trong các đầu ra là UTXO gắn với địa chỉ của Bob, trị giá 1 BTC. Ngay khi Bob thấy giao dịch này trên blockchain Bitcoin, anh ta trao chìa khóa cho Alice, và Alice lái xe đi. Như vậy có an toàn không? Alice có thể lấy được xe miễn phí không? Nếu có, hãy giải thích lý do. Nếu không, hãy giải thích Bob nên làm gì để đảm bảo anh ta được thanh toán.
F) → Alice sở hữu một chiếc Tesla mới hoàn toàn, mẫu Y. Cô ấy có thể dùng nó làm tài sản thế chấp để vay tiền trên hệ thống Compound ngay bây giờ (mà không cần bán nó) không? Nếu có, hãy giải thích cách làm. Nếu không, hãy giải thích lý do.
Câu 2. (20 điểm) Phát tán Byzantine.
Giả sử có n bên, với n > 3, trong đó một bên được chỉ định là người gửi (sender). Người gửi có một bit b ∈ {0,1}. Giao thức phát tán (broadcast) là quá trình các bên gửi thông tin cho nhau, và cuối cùng mỗi bên đều xuất ra một bit bi, với i = 1,...,n hoặc 0.
• Ta nói giao thức có tính nhất quán nếu với hai bên trung thực bất kỳ, nếu một bên xuất ra b và bên kia xuất ra b', thì b = b'.
• Ta nói giao thức có hiệu lực nếu khi người gửi trung thực thì tất cả các bên trung thực đều xuất ra bit bằng với bit đầu vào b của người gửi.
• Ta nói giao thức có tính phổ quát nếu khi một bên trung thực xuất ra một bit, thì cuối cùng tất cả các bên trung thực đều xuất ra một bit.
Một giao thức phát tán đáng tin cậy (RBC) là giao thức phát tán thỏa mãn ba đặc tính trên. Chúng ta giả sử tồn tại hạ tầng khóa công khai (PKI), nghĩa là mỗi bên đều có một khóa bí mật để ký, và mọi bên đều biết khóa công khai xác minh chữ ký chính xác của các bên còn lại.
Trong mạng đồng bộ, xét giao thức phát tán sau:
• Bước 0: Người gửi gửi bit đầu vào b cùng chữ ký của mình tới tất cả các bên còn lại. Sau đó người gửi xuất ra bit b và kết thúc.
• Bước 1: Mỗi bên không phải người gửi i gửi phản hồi thông tin mà họ nhận được từ người gửi đến các bên không phải người gửi khác, kèm theo chữ ký của i. Nếu họ không nhận được tin nhắn nào từ người gửi, họ không làm gì ở bước này. Tương tự, nếu tin nhắn từ người gửi bị lỗi (ví dụ chữ ký không hợp lệ hoặc nội dung không phải một bit đơn), thì các bên không phải người gửi cũng không làm gì ở bước này.
• Bước 2: Mỗi bên không phải người gửi thu thập tất cả các thông tin nhận được, tối đa n - 1 tin nhắn, trong đó tối đa một tin nhắn từ người gửi ở bước 0, và tối đa một tin nhắn từ mỗi bên không phải người gửi ở bước 1. Nếu nhận được hai tin nhắn từ người gửi có chữ ký hợp lệ nhưng chứa bit ngược nhau (tức là một tin nhắn ký bit 0, tin nhắn kia ký bit 1), thì người gửi không trung thực, và bên không phải người gửi xuất ra 0 và kết thúc. Ngược lại, nếu tất cả các bit được ký hợp lệ từ người gửi đều giống nhau, thì bên không phải người gửi xuất ra bit đó. Nếu bên không phải người gửi không nhận được tin nhắn nào, thì họ không xuất ra gì.
Đối với các câu hỏi sau, hãy mô tả một cuộc tấn công hoặc giải thích tại sao không thể bị tấn công.
A) Giả sử tối đa chỉ có một bên không trung thực, liệu giao thức vẫn đảm bảo tính nhất quán không?
B) Giả sử tối đa chỉ có một bên không trung thực, liệu giao thức vẫn đảm bảo tính hiệu lực không?
C) Giả sử tối đa có hai bên không trung thực, hãy chứng minh giao thức không đảm bảo tính nhất quán.
D) Giả sử tối đa có hai bên không trung thực, liệu giao thức có đảm bảo tính hiệu lực không?
E) Với bất kỳ số lượng bên không trung thực nào, liệu giao thức có đảm bảo tính phổ quát không?
Câu 3 (20 điểm): Thị trường tự động (AMM).
Bạn là nhà cung cấp thanh khoản trên Uniswap V2, đóng góp 5 ETH và 5000 DAI vào nhóm DAI/ETH. Giả sử 1 DAI = 1 USD, tổng vốn bạn bỏ vào là 10.000 USD.
A) Sau vài tháng, giá 1 ETH tăng lên 2000 DAI. Sau khi nhóm DAI/ETH điều chỉnh và ổn định theo tỷ giá mới, bạn quyết định rút toàn bộ phần vốn của mình. Giả sử hệ thống không tính phí (φ = 1), bạn sẽ nhận được bao nhiêu ETH và DAI?
B) Nếu bạn tự giữ 5 ETH và 5000 DAI, tài sản của bạn hiện tại sẽ trị giá 15.000 DAI, tức lợi nhuận 5000 DAI. Trong những tháng qua, so với chiến lược "tự giữ", bạn đã chịu tổn thất bao nhiêu khi làm nhà cung cấp thanh khoản trên Uniswap V2? Biểu diễn tổn thất theo giá trị tuyệt đối bằng USD, giả sử 1 DAI = 1 USD. Tổn thất này được gọi là tổn thất tạm thời, mặc dù trong trường hợp này nó gần như là vĩnh viễn.
C) Nếu bạn chịu tổn thất x USD khi làm nhà cung cấp thanh khoản trên Uniswap V2 (x được tính như ở phần (b)), thì số tiền đó đã đi đâu? Cụ thể, ai là người thu được x USD trong quá trình này?
D) Bây giờ chúng ta chuyển sang việc giao dịch trên Uniswap V2. Giả sử Bob dùng nhóm DAI/ETH để đổi một lượng lớn DAI sang ETH. Sau giao dịch, lượng DAI trong nhóm cao hơn trước, lượng ETH thấp hơn trước. Do đó, tỷ lệ tài sản trong nhóm DAI/ETH hơi lệch khỏi điểm cân bằng.
Người chênh lệch giá Alice phát hiện cơ hội này và muốn thực hiện một giao dịch ngược lại để tái cân bằng nhóm. Cô ấy muốn kiếm lời từ giao dịch này, vì vậy cô ấy muốn đảm bảo giao dịch của mình được thực hiện ngay sau giao dịch của Bob. Chiến lược này được gọi là "bám đuôi" (tail).
Alice có thể thực hiện kế hoạch bám đuôi như thế nào? Hãy đề xuất một phương pháp giúp giao dịch của Alice có khả năng cao được thực hiện ngay sau giao dịch của Bob.
E) Giả sử 10 người chênh lệch giá khác nhau, tất cả đều muốn tận dụng cơ hội chênh lệch do giao dịch của Bob tạo ra, thực hiện chiến lược bám đuôi giống nhau cùng lúc. Họ đều sử dụng cơ chế mà bạn mô tả ở phần (D). Vậy ai trong số 10 người này sẽ chiến thắng?
Câu 4. [16 điểm]: Lỗ hổng trùng nhập Hashmasks
Ở bài giảng 8 và mục 3, chúng ta đã thảo luận về lỗ hổng trùng nhập (reentrancy) trong Solidity. Trong câu hỏi này, chúng ta sẽ xem một ví dụ thực tế thú vị. Xét đoạn mã Solidity được dùng cho 16384 NFT sau đây. Bằng cách gọi hàm mintNFT() trên hợp đồng NFT này, người dùng có thể yêu cầu tối đa 20 NFT một lần. Bạn có thể giả sử tất cả các biến nội bộ đã được khởi tạo đúng bởi hàm khởi tạo (không hiển thị).
function mintNFT(uint256 numberOfNfts) public payable {
require(totalSupply() < 16384, "Sale has already ended");
require(numberOfNfts > 0, "numberOfNfts cannot be 0");
require(numberOfNfts <= 20, "You may not buy more than 20 NFTs at once"); require(totalSupply().add(numberOfNfts) <= 16384, "Exceeds NFT supply"); require(getNFTPrice().mul(numberOfNfts) == msg.value, "Value sent is not correct");
for (uint i = 0; i < numberOfNfts; i++) {
uint mintIndex = totalSupply(); // get number of NFTs issued so far
_safeMint(msg.sender, mintIndex); // mint the next one
} }
function _safeMint(address to, uint256 tokenId) internal virtual {
// Mint one NFT and assign it to address(to).
require(!_exists(tokenId), "ERC721: token already minted");
_data = _mint(to, tokenId); // mint NFT and assign it to address to
_totalSupply ++; // increment totalSupply() by one
if (to.isContract()) {
// Confirm that NFT was recorded properly by calling
// the function onERC721Received() at address(to).
// The arguments to the function are not important here.
// If onERC721Received is implemented correctly at address(to) then
// the function returns _ERC721_RECEIVED if all is well.
bytes4 memory retval=
IERC721Receiver(to).onERC721Received(to, address(0), tokenId, _data);
require(retval == _ERC721_RECEIVED, "NFT Rejected by receiver");
} }
Hãy chứng minh rằng _safeMint hoàn toàn không an toàn (mặc dù tên gọi là "an toàn").
A) Giả sử đã đúc 16370 NFT, vậy totalSupply() = 16370. Hãy giải thích cách một hợp đồng độc hại có thể khiến đúc hơn 16384 NFT. Kẻ tấn công có thể đúc tối đa bao nhiêu NFT?
Gợi ý: Nếu hàm onERC721Received tại địa chỉ được gọi là độc hại thì sao? Hãy kiểm tra kỹ vòng lặp đúc và xem xét lỗ hổng trùng nhập.
B) Giả sử giá trị totalSupply hiện tại là 16370, hãy viết mã hợp đồng Solidity độc hại thực hiện cuộc tấn công ở phần (a).
C) Bạn sẽ thêm hoặc thay đổi dòng mã Solidity nào trong đoạn mã ở trang trước để ngăn chặn cuộc tấn công? Lưu ý rằng một giao dịch không nên đúc quá 20 NFT.
Câu 5. (15 điểm) Câu hỏi về Bitcoin.
A) Lợi ích của giao thức Lightning Network là có thể thực hiện thanh toán mà không cần đăng giao dịch lên mạng Bitcoin. Liệu các thanh toán qua Lightning Network cuối cùng có thay thế hoàn toàn mọi giao dịch Bitcoin, khiến blockchain trở nên không cần thiết?
B) Như đã biết, một giao dịch Bitcoin có một tập hợp các địa chỉ đầu vào và một tập hợp các địa chỉ đầu ra. Thông thường, mỗi khóa đầu vào ủy quyền thanh toán cho toàn bộ giao dịch (trừ chữ ký). Loại chữ ký này được gọi là SIGHASH_ALL.
Ngược lại, giả sử mỗi khóa đầu vào chỉ ký phần đầu vào của giao dịch (Txin, không bao gồm chữ ký), mà không ký bất cứ điều gì khác — cụ thể là phần đầu ra (Txout) không được ký. (Loại chữ ký này gọi là SIGHASH_NONE).
Sau khi giao dịch được gửi đến mạng Bitcoin, với loại SIGHASH_NONE, thợ đào có thể đánh cắp tiền từ các địa chỉ đầu vào không? Nếu có, hãy giải thích cách thức. Nếu không, hãy giải thích lý do.
C) Nếu có người tìm ra cách giả mạo chữ ký ECDSA cho bất kỳ thông điệp nào chỉ với khóa công khai ECDSA, Bitcoin sẽ bị ảnh hưởng ra sao? Giả sử việc giả mạo một chữ ký mất 30 phút và không thể tăng tốc.
Câu 6. (11 điểm): Tornado Cash
Ở bài giảng 14, chúng ta đã học về máy trộn Tornado Cash. Nhắc lại rằng hợp đồng Tornado Cash cần lưu trữ danh sách lớn các nullifier, và mỗi lần rút tiền, một nullifier được lấy ra từ cây. Trong quá trình rút, hợp đồng cần đảm bảo rằng nullifier của vé rút chưa nằm trong danh sách các nullifier đã rút. Nếu chưa, hợp đồng thêm nullifier này vào tập hợp. Tornado Cash thực hiện bằng một ánh xạ:
mapping(bytes32 => bool) public nullifierHashes;
Trong quá trình rút, hợp đồng cần xác minh bằng chứng zk-SNARK được cung cấp, nếu hợp lệ thì thực hiện:
bytes32 _nullifierHash; // nullifier của vé đang rút require(!nullifierHashes[_nullifierHash], "The note has been spent"); nullifierHashes[_nullifierHash] = true;
A) Giả sử đã rút thành công k lần. Xét một thợ đào đang xác minh giao dịch Ethereum. Theo hàm của k, thợ đào này cần cấp phát bao nhiêu không gian lưu trữ để lưu ánh xạ nullifierHashes? Bạn có thể giả sử rằng ngoài ánh xạ này, hợp đồng Tornado không cần lưu trữ dài hạn nào khác.
B) Sẽ tốt hơn nếu chúng ta lưu trữ tập hợp nullifier đã rút Sk bên ngoài chuỗi, ví dụ như trên đám mây. Hợp đồng Tornado sẽ chỉ lưu trữ một cam kết ngắn về tập hợp nullifier Sk hiện tại. Khi gọi hàm rút, người dùng cung cấp tất cả tham số hiện tại, và thêm vào đó:
• Một bằng chứng π rằng nullifier nf của đồng tiền rút không nằm trong tập hợp đã cam kết, tức là nf ∉ Sk, và
• Thông tin đủ để hợp đồng Tornado tính được cam kết của tập hợp Sk+1 cập nhật: Sk+1 := Sk ∪ {nf}
Hợp đồng sẽ xác minh bằng chứng π rằng nf ∉ Sk, tính cam kết của Sk+1, và thay thế cam kết hiện tại của Sk bằng cam kết cập nhật của Sk+1.
Có một số cấu trúc dữ liệu cung cấp chức năng này, ví dụ cam kết của Sk là một giá trị hash 32 byte, và bằng chứng π chỉ gồm 2[log₂k] giá trị hash 32 byte. Ngoài ra, bằng chứng ngắn này cho phép hợp đồng Tornado tính cam kết ngắn của Sk+1. Một ví dụ có thể xây dựng từ cây Merkle Patricia đã giới thiệu ở bài 7, nhưng chúng ta sẽ để vấn đề này lại cho tương lai.
Mặc dù phương pháp này giảm mạnh kích thước lưu trữ của hợp đồng, nó chỉ đáng triển khai nếu làm giảm lượng gas cần thiết cho hàm rút. Xét các chi phí gas sau:
• Ghi vào mục không bằng không trong mảng lưu trữ: 20K gas
• Ghi vào mục khác không trong mảng lưu trữ: 5K gas
• calldata (mảng byte chứa tham số hàm): 16 gas mỗi byte
Giả sử chúng ta chỉ tính gas tiêu thụ bởi ba yếu tố liệt kê trên. Với k là bao nhiêu thì thay đổi này sẽ tiết kiệm được gas khi rút so với thực hiện hiện tại? Nhắc lại rằng bằng chứng π dài 32 × 2[log₂k] byte, và phải được đưa vào calldata của hàm rút.
C) Nhắc lại rằng Tornado Cash cung cấp một công cụ tuân thủ, cho phép người dùng làm mất ẩn danh đồng tiền của họ: công cụ này tạo một tệp liên kết khoản gửi của người dùng với một lần rút cụ thể. Trước khi sàn giao dịch chấp nhận tiền, tài liệu này có thể cần nộp cho sàn tập trung (ví dụ Coinbase).
Giả sử n người gửi một đồng tiền vào một nhóm Tornado, khi đó độ ẩn danh của nhóm là n (giả sử n = 1000). Sau đó, cả n người đều rút tiền về n địa chỉ Ethereum mới (mỗi địa chỉ mới nhận một đồng). Người quan sát không thể biết địa chỉ Ethereum mới nào ứng với người nào trong n người này, do đó tập ẩn danh có kích thước n.
Tuy nhiên, giả sử có n-1 người dùng công cụ tuân thủ và gửi tài liệu kết quả đến Coinbase. Điều này ảnh hưởng thế nào đến quyền riêng tư của người cuối cùng muốn giữ địa chỉ riêng tư?
Liên kết khóa học: https://cs251.stanford.edu/
Chào mừng tham gia cộng đồng chính thức TechFlow
Nhóm Telegram:https://t.me/TechFlowDaily
Tài khoản Twitter chính thức:https://x.com/TechFlowPost
Tài khoản Twitter tiếng Anh:https://x.com/BlockFlow_News
