TrueBit: scrypt-interactive implementation

Carl Park(4000D, github)

TrueBit은 EVM의 연산 성능의 한계를 극복하려는 스케일링 솔루션입니다. TrueBit에 대한 설명은 Decipher의 블록체인 확장성 솔루션 시리즈 5–1 :: Truebit A to Z를 참조하시면 좋을 것 같습니다. 이 글에서는 Doge-Ethereum bridge 를 구현한 scrypt-interactive 를 살펴보도록 하겠습니다. 해당 저장소는 PoC 를 목적으로 구현한 것이기 때문에 실제 Doge의 블록 데이터를 처리하거나, 저장하는 relayer 기능은 포함되어있지 않고 Scrypt 해쉬 함수를 TrueBit 프로토콜을 통해 verify하는 것을 목표로 하였습니다. relayer에 관한 컨셉은 이더리움의 BTCrelayer을 그대로 차용하였습니다.

Scrypt Hash Function

Scrypt는 주로 비밀번호를 hashing 하는데 사용됩니다. 이더리움에서 주로 사용되는 keccak과 다르게 계산 과정에서 메모리를 많이 사용하게 설계되어있습니다. 이는 이더리움이 PoW 알고리즘으로 Ethash를 사용하는 것과 동일한 맥락을 가집니다. 일반적인 컴퓨팅 환경이 아닌 ASIC을 이용하여 해쉬 함수를 더욱 빠르게 계산할 수 있는 알고리즘은 비트코인에서는 마이닝 풀의 중앙화를 일으키며, brute-force 공격을 통해 hash collision을 practical하게 발견할 수 있기 때문입니다. Scrypt를 사용하는 블록체인은 Litecoin, Dogecoin, Gridcoin, Auororacoin 등이 있습니다.

Doge는 Scrypt 함수를 그대로 사용하지 않고, 약간의 변형을 거쳐서 사용합니다.

scrypt-interactive overview

scrypt-interactive의 참가자, 컨트랙, 용어는 다음과 같습니다.

• Claimant: Doge 블록 데이터와 Scrypt 해쉬 결과를 이더리움에 등록하는 참가자입니다. BTCrelay의 relayer와 동일한 역할입니다.
• Verifier: Claimant가 제출한 블록 데이터와 Scrypt 해쉬 결과가 올바른지 검증하는 참가자입니다. TrueBit에서는 만약 결과가 올바르지 않다면 verification game을 통해 challenge 할 수 있습니다. (scrypt-interactive는 PoC이기 때문에 TrueBit의 인센티브 모델중 하나인 잭팟이 포함되어있지 않습니다.)
• DogeRelay: Doge 블록 정보들을 기록하는 이더리움 컨트랙입니다. 블록 데이터와 해쉬 결과가 올바른지 ClaimManager를 통해 검증받은 후 블록 정보를 Doge ERC20 컨트랙에게 전달합니다. (마찬가지로 PoC이기 때문에 DogeRelay이 완전하게 구현되어있지 않습니다. 블록을 전달하는 기능이 제외된 검증과정만 처리하는 DogeRelayDummy만 구현되어있습니다.)
• Doge ERC20: relay된 Doge 블록 데이터를 처리하는 토큰 컨트랙입니다. 마찬가지로 PoC에는 구현되어있지 않지만, processDogeTransaction함수를 통해 Doge 토큰을 발행할 것입니다.
• ClaimManager: Claim을 관리하는 컨트랙입니다. 만약 해당 Claim이 검증 된다면 DogeRelay 컨트랙에게 이를 알려줍니다.
• Claim: Claimant가 제출한 블록 정보들을 관리하는 구조체입니다. 해당 Doge블록 정보와 Claimant 에 관한 정보를 기록합니다. Verifier는 ClaimManager에 등록된 Claim들을 검증하고, 올바르지 않다면 verification game을 실행합니다. (실제 구현체의 이름은 ScryptClaim 입니다.)
• Session: verifier가 특정 Claim에 challenge를 시도할 경우 Session이 생성됩니다. Session은 verification game 정보를 관리하는 구조체이며 하나의 Claim은 여러 Session들을 가질 수 있습니다. 즉, 여러 Verifier가 동시에 challenge할 수 있습니다. verification game이 종료되면 ClaimManager에게 해당 Session의 결과가 결정되었음을 알려주고, challenge 패자의 deposit은 승자에게 전달됩니다. (실제 구현체의 이름은 VerificationSession 입니다.)
• Verification Game: Claimant와 Verifier가 Scrypt 해쉬 결과가 올바른지 검증하는 과정입니다. Doge의 Scrypt 해쉬 함수는 2048번의 연산을 요구합니다. Verifier가 특정 단계(step)의 연산 결과를 요청(Query)하면 Claimant는 이에 대해 응답(Respond)합니다. 응답할 때 특정 step의 연산 결과인 32바이트 해쉬를 알려줍니다. Verifier는 여러번의 요청을 통해 연산 결과가 달라지는 지점을 찾은 후 이를 ScryptVerifier 컨트랙에서 검증합니다.
• ScryptVerifier: Scrypt 함수를 실행하는 컨트랙입니다. 2048번의 모든 연산을 수행하지 않고 단 한번(1 step)의 연산만 수행합니다. 연산을 수행하기 전 상태(preState)와, 연산을 수행한 후의 상태(postState)를 입력으로 받은 후, 직접 연산한 결과가 postState와 동일한지 검사합니다. PoC단계에서 보이는 TrueBit은 어쨌든 EVM이 적어도 한번은 실행할 수 있는 계산에 대해서만 검증할 수 있는 한계를 가집니다.

두 참가자(Claimant, Verifier)는 ClaimManager에게 본인의 이더를 deposit 하고 bond한 후 verification game에 들어갑니다.

Contract Diagram

scrypt-interactive simple contract diagram

openzeppelin-solidity를 제외하면 scrypt-interactive에 구현된 컨트랙들은 위 다이어그램으로 간략하게 도식화할 수 있습니다. 실선은 상속관계를, 점선은 참조관계를 의미합니다. (참조는 다른 컨트랙의 함수 호출입니다.) 초록색과 파란색은 실제 배포된 컨트랙들을 의미하며, 초록색은 참여자들이 트랜잭션을 보내지 않고 단순히 call만 수행하는 컨트랙을 의미합니다.

• ScryptFramework: Scrypt 해쉬를 컨트랙에서 수행하기위한 기능들을 구현한 컨트랙입니다. Scrypt 해쉬를 위한 상태 저장, Proof 생성 들을 관리하며 generating mode와 verification mode를 가집니다. 각각 ScryptRunner, ScryptVerifier가 해당 기능들을 구현합니다.
• Verifier: Session을 관리하며 query, respond 함수를 구현합니다. Challenge의 승자 / 자를 결정하여 이를 ClaimManager에게 전달하기도 합니다. Claimant에 대응되는 Verifier와 관련이 없는 컨트랙입니다.
• ScryptRunner: ScryptFramework를 상속합니다. Scrypt 해쉬의 검증과정에 사용되지 않고 scrypt-interactive 참여자들이 Scrypt 연산 과정에서 사용되는 데이터들을 생성할 때 이용합니다. 주요 함수로 getStateAndProof, getStateProofAndHash, getStateHash 들이 있는데, 모두 pure modifier가 붙은, 클라이언트에서 사용되는 기능들입니다. 세 함수 모두 인자로 input 바이트와 특정 step을 가집니다. Verifier는 별도의 Doge의 Scrypt 해쉬 함수를 구현하지 않고 ScryptRunner를 이용하여 자체적으로 Claim을 검증할 수 있습니다.
• ScryptVerifier: Session을 관리하는 Verifier와 Scrypt 해쉬 함수를 구현한 ScryptFramework를 연결합니다. Scrypt와 연관된 verification game을 진행할 수 있습니다.
• IScryptDependent: scryptVerified함수가 정의된 인터페이스입니다. Claim이 올바르게 종료되어 Scrypt 해쉬 결과가 검증된다면 ClaimManager가 scryptVerified함수를 실행합니다.
• DogeRelayDummy: IScryptDependent를 상속하여 검증된 Doge 블록 정보를 처리하는 컨트랙입니다. 새로운 Doge 블록 정보(block bytes, block hash)가 들어오면 이를 ClaimManager에게 검증하도록 요구합니다. 미래의 DogeRelay 컨트랙은 scryptVerified 함수 내부에서 Doge ERC20 토큰을 발행할 것입니다.
• IScryptChecker: checkScrypt함수가 정의된 인터페이스입니다. 해당 함수는 DogeRelayDummy가 Scrypt 해쉬 결과의 유효성을 ClaimManager에게 요청할 때 사용합니다.
• DepositManager: 참여자들에게 deposit을 받거나 출금하는 컨트랙입니다. Claimant와 Verifier는 우선 deposit을 진행해야합니다.
• ClaimManager: IScryptChecker 인터페이스를 상속하여 DogeRelayDummy 컨트랙이 유호성 확인을 요청할 수 있습니다. DepositManager를 상속하여 참여자들에게 deposit을 받고 출금할 수 있습니다. 이 때 참여자들은 deposit을 사전에 bond해야 합니다. Claimant 혹은 verification game의 승패자들은 bond된 deposit을 기반으로 경제적인 incentive / disincentive 가 부여됩니다.

Verification Process

이제 실제로 Scrypt 해쉬 결과가 올바른지 검증하는 과정을 하나씩 살펴보겠습니다. 간략하게 <컨트랙 이름>.<함수 이름>: <from>으로 실행되는 함수의 위치를 표기하고 그 밑에 함수의 인자들을 적겠습니다. 실제 함수의 내용을 참조하기위한 github 링크도 걸려있습니다.

1. DogeRelayDummy.verifyScrypt: Claimant

function verifyScrypt(bytes _plaintext, bytes32 _hash, bytes32 proposalId) public payable

Claimant 가 새로운 Doge 블록의 데이터(_plainText)와 Scrypt 해쉬(_hash), 그리고 Claimant가 지정한 요청 ID(proposalId)를 인자로 verifyScrypt 함수를 호출합니다. 이 때 deposit을 위한 이더도 함께 보냅니다. 이는 BTCRelay에서 새로운 블록을 저장하는 storeBlockHeader와 동일한 의미를 가집니다.

DogeRelayDummy는 즉시 아래 함수를 호출합니다.

1.1 ClaimManager.checkScrypt: DogeRelayDummy

function checkScrypt(bytes _data, bytes32 _hash, bytes32 _proposalId, IScryptDependent _scryptDependent) public payable

마지막 인자인 _scryptDependent는 Scrypt의 유효성이 검증되면 호출할 scryptVerified 함수가 구현된 대상을 의미합니다. ClaimManager는 tx.origin(Claimant)의 deposit을 높인 후 새로운 Claim을 생성합니다. 이 때 발생한 ClaimCreated이벤트를 통해 Verifier들은 verification game에 참여할 지 판단할 수 있습니다.

2. ClaimManager.challengeClaim: Verifier

function challengeClaim(uint claimID) public

만약 1.1에서 생성된 Claim이 유효하지 않다면 Verifier가 challenge할 수 있습니다. 사전에 deposit을 한 후, challengeClaim함수에서 bond하게 됩니다. challengeClaim 함수는 해당 Claim의 challenger로 등록하는 것을 의미합니다.

3. ClaimManager.runNextVerificationGame: Anyone(But mostly Verifier)

function runNextVerificationGame(uint claimID) public

이제 누구나 runNextVerificationGame함수를 호출해 currentChallenger와 verification game을 시작할 수 있습니다. (말이 누구나지 Claimant가 직접 위 함수를 호출할 동기는 없습니다.)

ClaimManager는 아래 함수를 호출한 후 VerificationGameStarted 이벤트를 발생시킵니다.

3.1. Verifier.claimComputation: ClaimManager

function claimComputation(uint claimId, address challenger, address claimant, bytes _input, bytes _output, uint steps) public returns (uint)

함수의 구현은 Verifier 컨트랙에 되어있지만 호출 대상은 ScryptVerifier 입니다. 새로운 Session을 생성한 후 두 참여자간의 query와 respond를 기다립니다.

4. Verifier.query: Verifier

function query(uint sessionId, uint step) onlyChallenger(sessionId) public

특정 step의 연산 결과를 Claimant에게 요청합니다. 이 때 NewQuery 이벤트가 발생하며, Claimant가 특정 시간 이내에 응답하지 않는다면 timeout에 걸려 자동으로 Verifier가 승자가 됩니다.

query함수는 binary search 형식으로 요청할 수 있습니다. step은 처음엔 [0, 2048]의 범위를 가집니다. 그리고 이전에 Verifier가 step=10, step=20 의 query를 요청했다면, 세 번째 query의 범위는 [10, 20]안에 속해야합니다. 반복적인 query를 통해 binary search가 종료될 때 ([n, n+1]), EVM에서 Scrypt 해쉬를 한 번 수행하여 유효성을 검증합니다. (이 기능은 되어있습니다.)

5. Verifier.respond: Claimant

function respond(uint sessionId, uint step, bytes32 hash) onlyClaimant(sessionId) public

Verifier의 query에 대한 응답입니다. 이 때 hash는 Scrypt 해쉬 함수의 step번째 상태의 keccak 해쉬 입니다. 이는 session에 기록되며 binary search가 종료되는 시점에 lowHash(hash when step is N)와 highHash(hash when step is N+1)를 이용하여 두 시점의 Scrypt 해쉬 함수의 상태를 검증할 수 있습니다.

binary search가 종료되면 누구나 아래 함수를 호출할 수 있습니다.

6. Verifier.performStepVerification: Anyone

function performStepVerification(uint sessionId, uint claimID, bytes preValue, bytes postValue, bytes proofs, ClaimManager claimManager) public

preValue와 postValue는 Scrypt 해쉬 함수의 이전 / 이후 상태입니다. 4~5과정의 lowHash, highHash를 통해 Claimant가 제출한 respond와 동일한 상태 값들인지 검증할 수 있습니다.

(한가지 의문인 점은 Claimant가 의도적으로 잘못된 hash들을 제출할 경우, binary search가 종료된 후 6번 함수를 실행하기 위해서는 hash collision을 발견해야하지만 이는 practical하게 불가능합니다. 그럼 결국 timeout에 걸려 challenger가 패자가 됩니다.)

ScryptFramework가 구현한 runStep 함수를 이용하거나, 마지막 상태 값일 경우 Scrypt 해쉬 결과와 비교합니다. 이 때 결정된 패자가 Claimant인지 Verifier인지에 따라 아래 함수가 실행됩니다.

• ScryptVerifier.challengerConvicted: internal
• ScryptVerifier.claimantConvicted: internal

두 함수 모두 아래 함수를 호출한 후 해당 Session을 삭제합니다.

6.1. ClaimManager.sessionDecided: ScriptVerifier

function sessionDecided(uint sessionId, uint claimID, address winner, address loser) onlyBy(address(scryptVerifier)) public

패자의 bonded deposit을 승자에게 전달합니다. 그리고 다음 verification game을 다시 실행합니다(3번 과정). 패자가 Claimant인 경우 219라인에서 numChallenger에 0으로 할당하여 추가적인 verification game이 진행되지 않도록 조치합니다.

이 때 최종적으로 SesionDecided 이벤트를 통해 Verification Game이 올바르게 종료되었음을 알립니다.

7. ClaimManager.checkClaimSuccessful: Anyone

function checkClaimSuccessful(uint claimID) public

이제 충분한 시간이 지나고 verification game이 모두 종료되었다면 DogeRelayDummy 에게 Claim 결과를 알려줍니다(7.1번 과정). 251라인에서 Claimant가 패자인 경우(Scrypt 해쉬 결과가 올바르지 않은 경우)를 확인합니다.

7.1. DogeRelayDummy.scryptVerified: ClaimManager

function scryptVerified(bytes32 proposalId) public returns (uint)

이제 올바른 Doge 블록을 처리하여 Doge ERC20 토큰을 발행할 수 있습니다.

(다소 미흡한 점은 ClaimManager만 해당 함수를 호출할 수 있도록 조치하지 못한 것입니다.)

마치며

Doge-Ethereum bridge 의 PoC인 scrypt-interactive를 살펴보았습니다. 해당 저장소는 2월 12일을 마지막으로 더이상 업데이트가 되지 않고 있습니다. 사소한 이슈들이 몇가지 보이긴 하지만 Verification Game이 무엇인지 대략적인 이해를 돕기엔 충분한 자료인 것 같습니다. 한가지 아쉬운 점은 최종적인 검증을 위해서는 어쨌든 EVM을 사용해야한다는 것과 그를 위해서 ScryptFramework 같은 복잡한 컨트랙을 직접 구현해야만 한다는 것입니다. 추후 나올 구현물들에서는 분산 컴퓨팅 같은 특별한 HW / SW를 필요로

References

medium, 블록체인 확장성 솔루션 시리즈 5–1 :: Truebit A to Z
github, TrueBitFoundation/scrypt-interactive
github, ethereum/btcrelay
wikipedia, List of cryptocurrencies