스탠퍼드 대학교 CS251(암호화폐 및 블록체인 기술) 2021년도 기말 시험 문제
번역: TechFlow 인턴
스탠퍼드 명예 규정의 명시적 조항 및 정신에 따라, 저는 이번 시험에서 어떠한 도움도 받지 않았으며 다른 사람에게도 어떠한 도움도 제공하지 않았습니다.
서명: _________________________
• 본 시험은 총 6개의 문제로 구성되어 있으며, 만점은 100점입니다.
• 제한 시간 내에 시험을 완료해야 합니다.
• 답변은 Gradescope(D5GKRX)를 통해 제출하십시오.
• 질문에 답할 때는 간결하고 요점만 기술하십시오.
문제 1. (18점) 거시적 문제
A) → Rollup 시스템이 모든 트랜잭션을 체인 상에 저장하는 이유를 간단히 설명하시오. 만약 트랜잭션 데이터가 유실되고 다른 곳에 백업이 존재하지 않는다면 어떤 일이 발생하는가?
B) → 다음의 Solidity 코드를 보시오:
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);
}}
이 코드가 두 개의 계약(contract)에 배포되었다고 가정하자: 하나는 주소 X에 있는 계약이고, 다른 하나는 주소 Y에 있는 계약이다. 다음 중 어느 경우에 주소 X의 계약에서 _balances 상태를 읽을 수 있는가? 올바른 답을 고르시오(하나 이상).
A 주소 X에 있는 ERC20 계약의 _transfer() 함수 내 코드
B 주소 Y에 있는 ERC20 계약의 _transfer() 함수 내 코드
C etherscan.io를 사용하는 최종 사용자
C) → 위 문제에 이어, _transfer() 함수 호출 시 발생한 Transfer 로그 항목을 누가 읽을 수 있는가? 올바른 답을 고르시오.
A 주소 X에 정의된 ERC20 계약의 getBalance() 함수 내 코드
B 주소 Y에 정의된 ERC20 계약의 getBalance() 함수 내 코드
C etherscan.io를 사용하는 최종 사용자
D) → 두 개의 이더리움 트랜잭션 tx1과 tx2가 동시에 제출될 때, tx1의 maxPriorityFee를 y로 설정하고, tx2의 maxPriorityFee를 2y로 설정하면, tx2가 반드시 tx1보다 먼저 체인에서 실행되는가? 답하고 그 이유를 설명하시오. tx1과 tx2의 maxFee가 baseFee + maxPriorityFee보다 크다고 가정할 수 있다.
E) → 앨리스(Alice)가 딜러 밥(Bob)에게서 자동차를 사려 한다. 그녀는 비트코인 주소로 1비트코인을 전송한다. 밥은 다음 조건을 충족하는 트랜잭션을 기다린다: (1) 입력이 앨리스의 주소에서 오며, (2) 출력 중 하나가 밥의 주소에 바인딩된 1 BTC 가치의 UTXO이다. 밥이 비트코인 블록체인에서 해당 트랜잭션을 확인하면 열쇠를 앨리스에게 넘기고, 앨리스는 차를 몰고 갈 수 있다. 이것이 안전한가? 앨리스가 차를 공짜로 얻을 수 있는가? 가능하다면 이유를 설명하시오. 불가능하다면, 밥이 지불을 확실히 받기 위해 어떻게 해야 하는지를 설명하시오.
F) → 앨리스는 최신형 Y 모델 테슬라를 소유하고 있다. 그녀는 이를 담보로 Compound 시스템에서 대출을 받을 수 있는가 (판매하지 않고)? 가능하다면 방법을 설명하고, 불가능하다면 그 이유를 설명하시오.
문제 2. (20점) 비잔틴 브로드캐스트
n명의 참가자가 있고(n > 3), 그중 한 명이 송신자(sender)로 지정되어 있다고 하자. 송신자는 비트 b ∈ {0,1}를 갖고 있다. 브로드캐스트 프로토콜은 각 참가자가 서로 메시지를 주고받으며, 결국 각각 출력값 bi(i=1,...,n 또는 0)을 갖게 되는 프로토콜이다.
• 일관성(consistency): 두 성실한 참가자의 출력값이 각각 b와 b'라면, b = b'여야 한다.
• 유효성(validity): 송신자가 성실하다면, 모든 성실한 참가자의 출력값은 송신자의 입력 비트 b와 같아야 한다.
• 보편성(universality): 한 성실한 참가자가 비트를 출력하면, 결국 모든 성실한 참가자들이 비트를 출력하게 된다.
신뢰할 수 있는 브로드캐스트 프로토콜(RBC)은 위 세 가지 특성을 만족하는 브로드캐스트 프로토콜이다. 우리는 PKI(공개키 기반 구조)가 존재한다고 가정하며, 즉 각 참가자는 자신의 비밀 서명 키를 가지고 있고, 다른 참가자의 올바른 공개 서명 검증 키를 알고 있다.
동기 네트워크 환경에서 아래의 브로드캐스트 프로토콜을 고려해 보자:
• 단계 0: 송신자는 자신의 입력 비트 b를 다른 모든 참가자에게 (서명과 함께) 전송한다. 이후 송신자는 자신의 비트 b를 출력하고 종료한다.
• 단계 1: 각 수신자 i는 송신자로부터 들은 메시지를 다른 수신자들에게 전달하며, 이때 자신의 서명을 추가한다. 만약 송신자로부터 아무 메시지도 듣지 못했거나, 메시지가 손상되었을 경우(예: 서명이 무효하거나, 메시지가 단일 비트가 아닐 경우) 아무 작업도 수행하지 않는다.
• 단계 2: 각 수신자는 최대 n-1개의 메시지를 수집한다(단계 0에서 송신자로부터 최대 1개, 각 수신자로부터 최대 1개씩). 만약 송신자로부터 유효한 서명을 가진 두 개의 메시지를 받았는데 그 비트 값이 서로 다르다면(예: 하나는 0, 다른 하나는 1), 송신자는 부정직한 것으로 간주되며, 수신자는 0을 출력하고 프로토콜을 종료한다. 반대로, 송신자가 보낸 모든 유효한 메시지의 비트 값이 동일하면, 수신자는 그 비트 값을 출력한다. 만약 수신자가 아무 메시지도 받지 못했다면, 아무 것도 출력하지 않는다.
다음 질문들에 대해 공격 사례를 설명하거나, 공격이 불가능한 이유를 설명하시오.
A) 부정직한 참가자가 최대 1명이라고 가정할 때, 프로토콜은 여전히 일관성을 유지하는가?
B) 부정직한 참가자가 최대 1명이라고 가정할 때, 프로토콜은 여전히 유효성을 유지하는가?
C) 부정직한 참가자가 최대 2명이라고 가정할 때, 프로토콜이 일관성을 잃음을 보여라.
D) 부정직한 참가자가 최대 2명이라고 가정할 때, 프로토콜은 유효성을 유지하는가?
E) 부정직한 참가자의 수가 얼마든 상관없이, 프로토콜은 보편성을 가지는가?
문제 3 (20점): 자동화된 마켓 메이커(AMM)
당신은 Uniswap V2의 유동성 제공자로서 DAI/ETH 풀에 5 ETH와 5000 DAI를 제공하였다. 1 DAI = 1 달러라고 가정하면, 당신의 총 투자액은 1만 달러이다.
A) 몇 달 후, 1 ETH의 가격이 2000 DAI로 상승하였다. DAI/ETH 풀이 새로운 환율에 적응하여 안정된 후, 당신은 유동성 제공자로서의 전체 지분을 회수하기로 결정한다. 시스템 수수료가 없고(∅=1)라고 가정할 때, 당신은 몇 ETH와 몇 DAI를 받게 되는가?
B) 만약 당신이 원래의 5 ETH와 5000 DAI를 그대로 보유하고 있었다면, 현재 자산 가치는 15,000 DAI가 되어 5000 DAI의 이익을 얻었을 것이다. 그러나 Uniswap V2 유동성 제공자로서 이 기간 동안 "자체 보유" 전략과 비교했을 때 어떤 손실을 입었는가? 손실을 달러 단위의 절대값으로 표시하시오(1 DAI = 1 USD). 이러한 손실은 일시적 손실(temporary loss)이라 불리지만, 이 경우 실제로는 상당히 영구적인 손실이다.
C) Uniswap V2 유동성 제공자로서 x달러의 손실을 입었다면, 이 x달러는 어디로 간 것인가? 구체적으로, 누구에게 이 x달러가 귀속되었는가?
D) 이제 Uniswap V2에서의 거래로 넘어가자. 밥(Bob)이 DAI/ETH 풀을 이용해 큰 규모의 DAI를 ETH로 교환한다고 가정하자. 거래 후, 풀 내 DAI의 양은 다소 증가하고 ETH의 양은 다소 감소하여, 자산 비율이 균형점에서 벗어난다.
arbitrageur 앨리스(Alice)는 이 기회를 발견하고 반대 방향의 거래를 통해 풀을 재균형화하려 한다. 그녀는 이 거래에서 수익을 얻기를 원하므로, 자신의 거래가 밥의 거래 직후 바로 실행되도록 하고 싶다. 이러한 전략을 “꼬리물기(tailing)”이라 한다.
앨리스는 어떻게 꼬리물기 전략을 실행할 수 있을까? 앨리스의 거래가 밥의 거래 이후 합리적인 확률로 바로 실행되도록 할 수 있는 방법을 제안하시오.
E) 10명의 서로 다른 arbitrageur들이 밥의 거래로 인해 생긴 arbitrage 기회를 포착하기 위해 동시에 동일한 꼬리물기 전략을 실행한다고 가정하자. 모두 여러분이 (D)에서 설명한 메커니즘을 사용한다면, 이 10명 중 누가 성공할 것인가?
문제 4. [16점]: Hashmasks 재진입 결함
8강 3절에서 우리는 Solidity의 재진입(reentrancy) 결함에 대해 다뤘다. 이번 문제에서는 현실 세계의 흥미로운 예를 살펴볼 것이다. 아래는 16,384개의 NFT 중 하나에서 사용된 Solidity 코드 조각이다. mintNFT() 함수를 호출하면 사용자는 최대 20개의 NFT를 한 번에 발행할 수 있다. 모든 내부 변수는 생성자에 의해 올바르게 초기화되었다고 가정한다(생략됨).
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(); // 지금까지 발행된 NFT 수 가져오기
_safeMint(msg.sender, mintIndex); // 다음 NFT 발행
} }
function _safeMint(address to, uint256 tokenId) internal virtual {
// 하나의 NFT를 발행하고 주소(to)에 할당한다.
require(!_exists(tokenId), "ERC721: token already minted");
_data = _mint(to, tokenId); // NFT 발행 및 주소 to에 할당
_totalSupply ++; // totalSupply() 1 증가
if (to.isContract()) {
// 주소(to)의 onERC721Received() 함수를 호출하여 NFT가 올바르게 기록되었는지 확인
// 이 함수의 인자는 중요하지 않다.
// 만약 주소(to)에서 onERC721Received가 올바르게 구현되어 있으면
// 모든 것이 잘 되면 함수는 _ERC721_RECEIVED를 반환한다.
bytes4 memory retval=
IERC721Receiver(to).onERC721Received(to, address(0), tokenId, _data);
require(retval == _ERC721_RECEIVED, "NFT Rejected by receiver");
} }
이름은 'safe'하지만, _safeMint 함수는 전혀 안전하지 않음을 증명해보자.
A) 현재까지 16,370개의 NFT가 발행되어 totalSupply() = 16,370이라고 가정하자. 악의적인 계약이 어떻게 16,384개를 초과하는 NFT를 발행할 수 있는지 설명하시오. 공격자는 최대 몇 개의 NFT를 발행할 수 있는가?
힌트: 호출된 주소의 onERC721Received가 악의적이라면 무슨 일이 일어날까? 민팅 루프를 주의 깊게 검토하고 재진입 결함을 고려하시오.
B) 현재 totalSupply 값이 16,370이라고 가정하고, (a)의 공격을 수행하는 악의적인 Solidity 계약 코드를 작성하시오.
C) 귀하의 공격을 방지하기 위해 앞의 코드에서 어떤 줄을 추가하거나 수정해야 하는가? 단일 트랜잭션에서 20개를 초과하는 NFT가 발행되지 않도록 해야 한다.
문제 5. (15점) 비트코인 문제
A) Lightning Network 프로토콜의 장점은 비트코인 네트워크에 트랜잭션을 게시하지 않고도 결제를 수행할 수 있다는 것이다. Lightning Network 결제가 궁극적으로 모든 비트코인 트랜잭션을 대체하여 블록체인 자체를 불필요하게 만들 수 있는가?
B) 일반적으로 비트코인 트랜잭션은 일련의 입력 주소와 출력 주소를 갖는다. 각 입력 주소는 서명을 제외한 트랜잭션 전체를 승인할 수 있다. 이 서명 유형을 SIGHASH_ALL이라 한다.
반대로, 각 입력 주소의 키를 사용하여 Txin(트랜잭션 입력 부분, 서명 제외) 전체에 서명하고, 그 외에는 아무것도 서명하지 않는다고 가정하자. 즉, Txout(출력 부분)은 서명되지 않는다. (이 서명 유형은 SIGHASH_NONE이라 함)
트랜잭션이 비트코인 네트워크에 제출된 후, SIGHASH_NONE 방식을 사용한 트랜잭션의 경우 마이너가 입력 주소에서 자금을 훔칠 수 있는가? 가능하다면 어떻게 훔치는지 설명하고, 불가능하다면 그 이유를 설명하시오.
C) ECDSA 공개키만으로 임의 메시지에 대한 ECDSA 서명을 위조하는 방법을 누군가 발견했다고 가정하자. 서명 하나를 위조하는 데 30분이 걸리며 더 빠르게 만들 수 없다면, 비트코인은 어떤 영향을 받는가?
문제 6. (11점): Tornado Cash
제14강에서 우리는 Tornado Cash 믹서(mixer)에 대해 배웠다. Tornado Cash 컨트랙트는 large nullifiers 리스트를 저장해야 하며, 매 인출 시 트리에서 nullifier를 추출한다. 인출 과정에서 컨트랙트는 인출된 노트의 nullifier가 이미 인출된 nullifier 목록에 없는지 확인해야 한다. 만약 없다면, 컨트랙트는 해당 nullifier를 집합에 추가한다. Tornado Cash 컨트랙트는 이를 다음과 같은 맵핑으로 구현한다:
mapping(bytes32 => bool) public nullifierHashes;
인출 과정에서 컨트랙트는 제공된 zk-SNARK 증거를 검증해야 하며, 증거가 유효하면 다음과 같이 처리한다:
bytes32 _nullifierHash; // 인출되는 노트의 nullifier require(!nullifierHashes[_nullifierHash], "The note has been spent"); nullifierHashes[_nullifierHash] = true;
A) 트리에서 k번 성공적으로 인출했다고 가정하자. 이더리움 트랜잭션을 검증하는 마이너는 nullifierHashes 맵핑을 저장하기 위해 k의 함수로 얼마나 많은 저장 공간을 필요로 하는가? Tornado 컨트랙트가 이 nullifierHashes 맵핑 외에는 장기 저장이 필요하지 않다고 가정할 수 있다.
B) 인출된 nullifier Sk를 클라우드 등 체인 외부에 저장할 수 있다면 더 좋을 것이다. Tornado 컨트랙트는 현재의 nullifier 집합 Sk에 대한 짧은 커밋만 저장한다. 인출 함수 withdraw() 호출 시 사용자는 기존 파라미터 외에도 다음을 제공해야 한다:
• 인출되는 코인의 nullifier nf가 커밋된 nullifier 집합에 포함되지 않았다는 증명 π, 즉 nf ∉ Sk,
• Tornado 컨트랙트가 업데이트된 nullifier 집합 Sk+1 := Sk U {nf}에 대한 커밋을 계산할 수 있는 충분한 정보
컨트랙트는 π를 검증하여 nf ∉ Sk임을 확인하고, Sk+1에 대한 커밋을 계산한 후, 기존 Sk 커밋을 Sk+1 커밋으로 대체한다.
Sk의 커밋은 32바이트 해시값이며, 증명 π는 2[log₂k]개의 32바이트 해시값으로 구성될 수 있다. 또한 이 짧은 증명을 통해 Tornado 컨트랙트는 Sk+1의 짧은 커밋을 계산할 수 있다. Merkle Patricia 트리를 변형하면 이러한 기능을 구현할 수 있으나, 여기서는 그 세부사항을 생략한다.
이 방법은 컨트랙트의 저장 공간을 크게 줄이지만, 인출 함수의 가스 비용을 줄일 수 있을 때만 실현 가치가 있다. 다음 가스 비용을 고려하시오:
• 저장 배열의 0항목 쓰기: 20K 가스
• 저장 배열의 비제로 항목 쓰기: 5K 가스
• calldata (함수 인자의 바이트 배열): 1바이트당 16 가스
위 세 가지 항목의 가스 소비만을 고려한다고 가정하자. 인출 실행 방식을 변경했을 때, k의 함수로 얼마나 많은 가스를 절약할 수 있는가? 증명 π는 32 × 2[log₂k] 바이트이며, 인출 함수의 calldata 일부로 제공되어야 함을 기억하시오.
C) Tornado Cash는 사용자가 자신의 코인을 익명 해제할 수 있는 컴플라이언스 도구를 제공한다: 이 도구는 사용자의 예치금을 특정 인출과 연결하는 파일을 생성한다. 거래소(Coinbase 등)에서 자금을 수락하기 전에 이 문서를 제출해야 할 수 있다.
n명의 사람이 Tornado 풀에 코인을 예치하였고, 익명 집합 크기는 n(n=1000)이라고 하자. 이후 모든 n명이 각각 새로운 이더리움 주소로 코인을 인출한다(각 주소에 코인 하나). 관찰자는 어떤 새 주소가 n명 중 누구에게 해당하는지 알 수 없으므로 익명 집합 크기는 n이다.
그러나 n-1명이 컴플라이언스 도구를 사용하여 결과 문서를 Coinbase에 보내는 경우, 마지막으로 남은 개인의 프라이버시는 어떻게 되는가?
강의 링크: https://cs251.stanford.edu/
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
