Ethereum [2] (Algorithm, Protocol)

※ 원글 작성 : 22년 4월 27일

Recursive Length Prefix

• 다양하고 복잡한 형식의 데이터를 하나의 정형화된 형식으로 직렬화 후 저장/전송
• 바이너리 데이터로 표현
• 이더리움 헤더의 state root, transaction root, receipt root 등과 통신 프로토콜 상 메시지 등 이더리움에서 전체적으로 사용
• Definition
  • 값이 단일 바이트일 경우, [0x00, 0x7f] 해당 바이트를 그대로 적용
  • String 길이가 0~55바이트인 경우 0x80 스트링 길이를 더한값을 앞에 붙이고 이어서 string을 붙임(dog = 0x80 + 0x03이 앞에)
  • String이 55바이트를 초과하는 경우 0xb7 단일 바이트에 문자열 길이 바이트를 더한 다음, 문자열 길이 + string으로 구성
• e.g.
  • null(empty string) = [0x80]
  • Empty list = [0xc0]
  • Integer 0 = [0x80]
  • String 'dog' = [0x83,'d','o','g']
  • list['cat','dog'] = [0xc8,0x83,'c','a','t','0x83','d','o','g']
  • String "Lorem ipsum dolor sit amet, consectetur adipiscing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]
• 장점
  • 다양한 인코딩 방식에 비해 과정 단순
  • 바이트 단위의 일관성 확보

Merkle Patricia Tree

• 모든 단어를 기록하는것 보다 공통 부분 공유하는것이 공간 절약
• account 등의 저장에 사용, 중복 부분 제거 가능
• 트리 구조
  

  

  ethereum.org

  • Leaf node : encoding path > value
  • Extension node : encoidng path > key
  • Branch node : [0...f] 상에서 16개는 다음노드 key, 마지막은 value
  • e.g.
    • A7 > 1 > 1355 : 45.00ETH
    • A7 > 7 > d3 > 3 > 7 : 1.00wei

HP(Hex Prefix) encoding

• MPT의 경로를 만들기 위해 사용
• e.g.
  • Path : 3-2-3 = Whale
    Root: {1: 'Dog', 2: B, 3: A}
    A: {1: C, 2: D, 3: 'Cat'}
    B: {1: 'Goat', 2: 'Bear', 3: 'Rat'}
    C: {1: 'Eagle', 2: 'Parrot', 3: E}
    D: {1: 'Shark', 2: 'Dolphin', 3: 'Whale'}
    E: {1: 'Duck', 2: 'Chinken', 3: 'Pig'}
• 구조
  • key : 좌측 key (Root, A, B ..)
  • Node : 키와 관련된 오른쪽 요소 ({1:'Dog'...)
  • Value : 모든 노드에 일부 요소 존재
  • Nibble : 4bit의 hex form
• RLP와의 차이
  • RLP : Value를 encoding/decoding
  • HP : Path를 encoding/decoding
• HP 목적
  • Leaf노드와 extension노드를 구분하기 위해서 선행 구분자를 붙이기 위함

Bloom filter

• 특정 원소가 집합에 속하는지 검사하는데 사용 가능한 확률형 자료 구조
• 집합의 크기나 원소의 크기가 커서 원소가 집합에 속하는지 판단에 시간이 걸리는 경우 전처리 과정으로 Bloom filter 사용
• 이더리움 상에서 수많은 트랜잭션 중 검색한 트랜잭션을 확인 전에 전처리로 블룸필터 사용

Gas

• EVM 상에서 트랜잭션 동작을 위한 수수료
• Ethereum에서 무한 loop에 빠지는 것을 방지하기 위해 gas를 도입
• 트랜잭션 처리 및 내부 명령어 실행 시 gas를 소모
• Block gas limit(2019기준)
  • 한 블록에 담을 수 있는 gas 총량
  • 한 블록 당 가스 총량 = 6,700,000
  • 한 트랜잭션 당 최소 처리 비용 = 21,000
  • 블록 하나 당 최대 319개 처리
• 트랜잭션 수행 시 가스 사용 과정
  

  

  springer

  • Gas limit 값으로 가스값 초기화
  • gasLimit * gasPrice에 해당하는 양을 사용자의 account에서 차감
  • 트랜잭션 수행되며 가스 소모
  • 최종 트랜잭션 수행된 후 남은 가스는 사용자에게 반환
  • 소모된 가스비는 miner에 수수료로 전달
• 트랜잭션 취소 과정
  

  

  springer

  • 가스를 다 사용하면 진행중인 트랜잭션 실행 취소, revert 되어 트랜잭션 이전 상태로 돌아감
  • 사용한 가스는 miner에 수수료로 전달, 반환 안됨

Hashed time lock

• 계약을 일정 시간까지로 제한한 '타임락'과 일정한 해시값이 제시되야 계약이 성사되는 '해시락'이 결합한 형태
• HTLC(contract or channel)
• 특정 상대에게 코인을 보내면서 실제로 보내지는 지점에 제한을 걸어두고(타임락), 그 시점가지 상대방에게 코인을 보내지 않으면 거래가 이루어지지 않게함(해시락)
• 서로 다른 블록체인 간 atomic swap을 가능하게 하며, 수신자에게 두가지중 하나를 요구
  • 지급 행위의 암호학적 증명으로 생성된 데드라인 전가지 지급 행위를 받아들여 인정
  • 지급 행위 요구에 대한 능력을 박탈당하여 지급 행위자에게 다시 돌아가는 것
• e.g.
  

  

  hash.kr

Kademlia

• P2P 네트워크를 위한 분산해시테이블(DHT)을 구축하는 프로토콜
• 카뎀리아 노드들은 네트워크 구조 및 노드 탐색을 통한 정보 교환을 UDP로 통신, 참여 노드 간에 가상/오버레이 네트워크를 형성
• 특징
  • 네트워크의 노드가 빠르고 정확하게 대상 노드를 검색 및 도달
  • UDP를 이용하여 서로 통신
  • 노드 ID로 구분
    • ID가 노드를 식별하는것 뿐만 아니라 카뎀리아 알고리즘이 value(file hash or keyword)의 위치를 찾는데도 사용
    • 노드 ID는 파일 해시에 대한 direct map으로 파일 또는 resource를 어디서 획득 할 수 있는지 확인
  • Value를 찾을 때 알고리즘은 몇번의 단계를 거쳐 네트워크를 탐색
    • 각 단계는 key와 더 가까운 노드를 탐색하는 작업으로 연결된 노드가 찾던 값을 반환
    • 또는 더 가까운 노드를 찾을 수 없을 때 까지 반복
• 이더리움에서는 노드 discovery 시에 카뎀리아 일부를 수정해서 사용
• 노드 간의 거리를 XOR로 측정
  • A가 생각하는 B까지의 거리, B가 생각하는 A까지의 거리, C가 생각하는 A-B간의 거리는 같음
  • 각 노드는 자신이 알고 있는 노드 중에서 자신과 가까운 노드들과 통신하면 적은 연결 수로도 큰 네트워크를 구성할 수 있음

Node discovery

• 단계
  • PING : 상대 노드가 live인지 확인
  • STORE : 노드에 key value 저장
  • FIND_NODE : 요청된 노드에 가장 가까운 노드를 return
• 처음 노드가 mainnet에 합류할 시 설정된 bootnode에게 주변 live node의 리스트를 request하여 통신
• // go-ethereum/cmd/bootnode/main.go // bootnode 상에서 node key 확인 natm, err := nat.Parse(*natdesc) if err != nil { utils.Fatalf("-nat: %v", err) } switch { case *genKey != "": nodeKey, err = crypto.GenerateKey() if err != nil { utils.Fatalf("could not generate key: %v", err) } if err = crypto.SaveECDSA(*genKey, nodeKey); err != nil { utils.Fatalf("%v", err) } if !*writeAddr { return } case *nodeKeyFile == "" && *nodeKeyHex == "": utils.Fatalf("Use -nodekey or -nodekeyhex to specify a private key") case *nodeKeyFile != "" && *nodeKeyHex != "": utils.Fatalf("Options -nodekey and -nodekeyhex are mutually exclusive") case *nodeKeyFile != "": if nodeKey, err = crypto.LoadECDSA(*nodeKeyFile); err != nil { utils.Fatalf("-nodekey: %v", err) } case *nodeKeyHex != "": if nodeKey, err = crypto.HexToECDSA(*nodeKeyHex); err != nil { utils.Fatalf("-nodekeyhex: %v", err) } } // node discover db, _ := enode.OpenDB("") ln := enode.NewLocalNode(db, nodeKey) cfg := discover.Config{ PrivateKey: nodeKey, NetRestrict: restrictList, } if *runv5 { if _, err := discover.ListenV5(conn, ln, cfg); err != nil { utils.Fatalf("%v", err) } } else { if _, err := discover.ListenUDP(conn, ln, cfg); err != nil { utils.Fatalf("%v", err) } }

Account address

• 절차
  • Private key 생성
  • Private key로 부터 Public key 생성
  • Public key로 account address 생성
    • Public key에 keccak256 hash 적용
    • 계산된 hash의 하위 20bytes를 account address로 사용
• 굳이 긴 bytes의 address로 사용할 필요 없음 (주소 20bytes, Hex 인코딩 시 40bytes)
  • Transaction 내의 signature로 pub key를 확인 가능하여 공격자가 Tx를 가로챌 수 있지만, Tx는 수신자에게 ETH를 이체하는 것이고 gas fee도 지불해야해서 TX를 가로챌 의미가 없음
• EIP-55 (Checksum)
  • 이더리움 account address에 대한 이전 버전 호환 체크섬
  • 방법
    • 0x를 제외한 주소의 keccak256 hash 생성
    • Hash가 0x8과 같거나 큰경우 대문자로 변경
    • 주소의 모든 문자를 같은 자리 해시와 비교하여 대문자로 변경할 수 있는 값을 대문자로 변환

Receipt

• 블록 저장 정보

  {
  "jsonrpc": "2.0",
  "id": 1,
  "result": {
  "blockHash": "0xc5e5a515898983d1370d40b03fc05ae08be861af746a1577796153a149a1bb20",
  "blockNumber": "0x5ff5dd",
  "contractAddress": null,
  "cumulativeGasUsed": "0xe85fb",
  "from": "0xd7afd4441fccc118b9207b0e136f4ef9319b3c79",
  "gasUsed": "0x9034",
  "logs": [
    {
      "address": "0x0d8775f648430679a709e98d2b0cb6250d2887ef",
      "topics": [
        "0xddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef",
        "0x000000000000000000000000d7afd4441fccc118b9207b0e136f4ef9319b3c79",
        "0x00000000000000000000000069d9e9aff57ec73582ad1ce441726dba7ea78fe0"
      ],
      "data": "0x0000000000000000000000000000000000000000000001054aefee8ba6d00000",
      "blockNumber": "0x5ff5dd",
      "transactionHash": "0x3265c1461d3f167c756fbc062ae3a2dc279b44a9c3ca2194271d4251cd0c1655",
      "transactionIndex": "0x1b",
      "blockHash": "0xc5e5a515898983d1370d40b03fc05ae08be861af746a1577796153a149a1bb20",
      "logIndex": "0xa",
      "removed": false
    }
  ],
  "logsBloom": "0x04000000002000000200000000000000002000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000008000000000000080000000000000000000000000000000000000000000000000000000000000000000000000000200010000000000000000000000000000000000000000000000100000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000",
  "status": "0x1",
  "to": "0x0d8775f648430679a709e98d2b0cb6250d2887ef",
  "transactionHash": "0x3265c1461d3f167c756fbc062ae3a2dc279b44a9c3ca2194271d4251cd0c1655",
  "transactionIndex": "0x1b"
  }
  }

• eth_getTransactionReceipt
• 항목
  • blockHash/blockNumber : 트랜잭션 저장 블록/블록 넘버
  • contractAddress : 컨트랙트 주소
  • cumulativeGasUsed : 전체 거래에서 사용한 가스 사용량(SC 호출 시 발생 가스 소비량도 합)
  • from : 송신자 주소
  • gasUsed : 거래에 사용된 가스
  • transactionHash : 트랜잭션 hash

Log/Event

• Solidity event function으로 생성가능
• event hash를 통해 로그 검색/조회하면 해당 event가 발생했을 시의 로그 출력

참고
https://eth.wiki/en/fundamentals/rlp
https://hamait.tistory.com/959
https://medium.com/coinmonks/data-structure-in-ethereum-episode-1-compact-hex-prefix-encoding-12558ae02791
http://wiki.hash.kr/index.php/%EB%8C%80%EB%AC%B8
https://preethikasireddy.medium.com/how-does-ethereum-work-anyway-22d1df506369
https://kr.zastrin.com/courses/ethereum-primer/lessons/2-3