COMP90088 Cryptocurrencies and Decentralised Ledgers (Semester 1 2022)
Homework 3
due: 2022-04-28 22:00 (AEST)
1 Ethereum data structures (1.75 marks)
Copyright By PowCoder代写 加微信 powcoder
Ethereum replaces Bitcoin’s standard Merkle trees with “ ATRICIA trees” also known as radix tries, prefix trees, tries, and by several other names. Ethereum’s specific implementation maps 256bit keys (or paths) to 256bit values. Below we introduce standard PATRICIA trees, which can be extended to ATRICIA trees through the use of hash pointers in the same way that binary trees are extended to binary Merkle trees. A PATRICIA tree allows three types of nodes:
• empty nodes (omitted from the diagram below),
• branch nodes, which store a data value (which may be empty, represented by ∅ in the diagram below), and an array of 16 node pointers, each pointing to a child node or NULL otherwise. The data value is mapped to by the key represented by the path to this node from the root. Each child of this node extends said key by one nibble (4 bit), defined by its position in the pointer array. In the figure below, branch nodes are shown in blue, with their data value drawn within. Non-NULL child pointer entries are shown as directed edges labelled by the index in this node’s pointer array.
• kv nodes, which include a partial key of arbitrary length, and either a pointer to a branch node or a data value (making the node a leaf). The partial key extends the key represented by the path to this node from the root. These nodes are shown in pink below.
In the following example, 9 key-value pairs with non-empty values are present, with 13098a mapped to “c” and 444 to “d”:
a. Explain why in the above example that there is no label on the arrow coming out of the intermediate kv node at the path 4.
b. What data would you need to supply for a proof that the key 44431337a has no value mapped to it? How about the keys fc and 1a3098a?
c. Given random keys of arbitrary length, the average-case proof lengths (for both absence and presence) are O(logn) for a tree with n items, as desired. However, constants may vary. Describe a worst-case tree with just k keys that requires proofs of length O(k).
Ethereum uses 160 bit addresses for contracts and owned accounts. Explain why this worst- case proof time is not a serious problem for the tree which stores account state, also known as the state trie.
Explain why this does not hold for the trees maintaining the long-term storage for each contract (addressable by 256 bit addresses), also known as the storage tries. How might you write a malicious contract which stores k words in memory and then makes a single write which is as expensive as possible?
Atomic cross-chain exchange (2 marks)
OP_CHECKLOCKTIMEVERIFY is a new Bitcoin instruction (added via soft fork) which examines the top item on the stack and, if it is greater than the current block’s timestamp1, halts execution with an error. If not, it is a NOP (it is also a NOP for any old client that has not adopted the soft fork). Consider the following Bitcoin scriptPubKey (assuming Bob gets to choose Y):
OP_DROP // Needed to discard t1 from the stack
OP_CHECKSIG OP_ELSE
OP_SHA256
OP_EQUALVERIFY
OP_CHECKSIG OP_ENDIF
1 2 3 4 5 6 7 8 9
10 11 12 13
1 2 3 4 5 6
Explain the conditions under which this transaction output can be spent.
HowcouldyouachieveasimilareffectwithBitcoinpriortotheavailabilityofOP_CHECKLOCKTIMEVERIFY? What were the downsides of the old way?
Alice and Bob can use this transaction to achieve atomic exchange of Bitcoin for Ether. Alice will send her Bitcoin to a transaction output with the above script. Bob will send his Ether to a special (one-time use) smart contract sketched below. Either Bob should end up with Alice’s Bitcoin and Alice with Bob’s Ether, or neither should change hands.
contract CrossChain {
uint256 t2, y; address alice , bob;
function AliceRedeem(uint256 x) public {} // implement this function BobRedeem () public {} // implement this
Assuming that the storage variables are suitably initialised, implement the two functions AliceRedeem and BobRedeem. Neither should be longer than 5 lines.
How should Y be chosen by Bob?
Should Alice fund her transaction first or should Bob fund the CrossChain contract first?
Should the timestamp t1 be greater than, less than, or equal to the timestamp t2? If they are different, how large should the difference be?
Ethereum bug hunting (1.25 marks)
The contract code presented below is an attempt to implement a two-player game (with a wager on the line) of Tic-Tac-Toe, also known as Noughts and Crosses. This implementation contains at least 9 bugs which compromise the security of the game. Identify 5 bugs and briefly describe how they might be fixed. Recall that Ethereum initialises all storage to zero. Assume that the function checkGameOver is correctly implemented and returns true if either player has claimed three squares in a row on the current board.
1It is possible to use OP_CHECKLOCKTIMEVERIFY with either a block number or timestamp, but here we’ll just assume we’re using a timestamp.
contract TicTacToe {
// game configuration
address[2] _playerAddress; // address of both players
uint32 _turnLength; // max time for each turn
// nonce material used to pick the first player
bytes32 _p1Commitment; uint8 _p2Nonce;
// game state
uint8[9] _board; // serialized 3×3 array
uint8 _currentPlayer; // 0 or 1, indicating whose turn it is uint256 _turnDeadline; // deadline for submitting next move
// Create a new game, challenging a named opponent.
// The value passed in is the stake which the opponent must match.
// The challenger commits to its nonce used to determine first mover. constructor(address opponent , uint32 turnLength ,
_playerAddress[0] = msg.sender;
bytes32 p1Commitment) public {
_playerAddress[1] = opponent; _turnLength = turnLength;
_p1Commitment = p1Commitment; }
// Join a game as the second player.
function joinGame(uint8 p2Nonce) public payable { // only the specified opponent may join
if (msg.sender != _playerAddress[1]) revert();
// must match player 1’s stake. require (msg.value >= this.balance);
_p2Nonce = p2Nonce; }
// Revealing player 1’s nonce to choose who goes first.
function startGame(uint8 p1Nonce) public { // must open the original commitment
require(sha3(p1Nonce) == _p1Commitment);
// XOR both nonces and take the last bit to pick the first player
_currentPlayer = (p1Nonce ^ _p2Nonce) & 0x01;
// start the clock for the next move
_turnDeadline = block.number + _turnLength; }
// Submit a move
function playMove(uint8 squareToPlay) public {
// make sure correct player is submitting a move require (msg.sender != _playerAddress[_currentPlayer]);
// claim this square for the current player.
_board[squareToPlay] = _currentPlayer;
// If the game is won, send the pot to the winner if (checkGameOver())
selfdestruct(msg.sender);
// Flip the current player _currentPlayer ^= 0x1;
// start the clock for the next move
_turnDeadline = block.number + _turnLength; }
// Default the game if a player takes too long to submit a move
function defaultGame() public {
if (block.number > _turnDeadline)
selfdestruct(msg.sender);
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com