[MIT OCW] 1 . Signatures, Hasing, Hash Chains, e-cash, and Motiviation

이 글은 MIT OpenCourseWare 의 MAS.S62 - Cryptocurrency Engineering and Design의 강의를 요약, 정리 한 것입니다..

글을 읽으실 때 이해를 위하여 원 강의를 함께 보시는 것을 추천합니다.

*글에 포함된 이미지는 강의에서 제공되는 Lecture Note로부터 캡쳐한 것입니다.

 

*최신수정 : 2025/1/2 (목) : 가독성 향상을 위해 추후 수정 예정

 

1강의 내용은 크게 3가지로, "거래 시스템, 해싱, 서명"으로 이루어져있습니다.

강의의 시작에 앞서 비트코인의 특성이나 Money가 보유하는 특성등의 내용이 있었으나, 이는 생략합니다.

 

1. 거래 시스템

이 강의에서는, Alice와 Bob이라는 두 인물이 금융거래를 할 때 일련의 과정들을 설명합니다.

1) 은행을 통한 현재의 거래 방식

현 세대에서 디지털 결제가 작동하는 방식은 신뢰하는 기관(ex. 은행)에 의해 이뤄집니다.

Alice가 Bob에게 5$를 지불하기로 했다면, Alice는 은행에 5$를 Bob에게 송금하라는 요청을 보낼 것이고, 은행은 이를 확인 한 후, 본인들의 장부 상에서의 값을 변경할 것입니다. 이후 Bob은 은행의 장부를 확인함으로써 송금을 확인할 수 있습니다. 이 과정을 순차적으로 정리하자면,

 

• 사용자 인증: 거래 당사자(송신자 - Alice와 수신자 - Bob)가 은행 계좌를 보유하고 있으며, 은행은 이들의 신원을 알고 있습니다.
• 거래 요청: 송신자 - Alice가 은행에 거래 요청을 보냅니다.
• 잔액 확인: 은행은 송신자 - Alice의 계좌에서 충분한 잔액이 있는지 확인합니다.
• 거래 승인: 은행이 거래를 승인하고 송신자-Alice의 계좌에서 금액을 차감합니다.
• 수신자 계좌 입금: 수신자-Bob의 계좌에 해당 금액이 입금됩니다.
• 기록 저장: 은행은 모든 거래 내역을 중앙 데이터베이스에 기록합니다.

 

현재 은행의 거래과정의 장단점은 아래와 같습니다.

pros

 - Digital payment (디지털거래를 통한 편의)

cons

 - Not Peer-to-Peer (은행은 모든 거래가 일어날 때 항상 온라인이어야함)

 - 은행의 파산 위험

 - 특정 거래에 대한 지연 혹은 거부 가능

 - 프라이버시 노출(은행이 모든 신원을 보유)

 

2) e-cash

e-cash(은행으로부터 Serial Number가 적힌 token을 받아 금융거래를 수행)를 활용하게 되는 경우,

 

• e-cash 발행: 사용자는 은행 또는 발행 기관에서 e-cash를 구매하고 디지털 토큰 형태로 보유합니다.
• 사용자 인증: 송신자는 거래 시 발행 기관에서 발급받은 인증을 사용.
• 거래 실행: 송신자가 수신자에게 e-cash를 전송합니다.
• 잔액 검증: 발행 기관은 토큰의 유효성과 중복 사용 여부를 검증합니다.
• 수신자 수령: 수신자가 e-cash를 수령하고 발행 기관에 잔액 확인 요청을 할 수 있습니다. 

e-cash를 활용하는 경우, peer to peer 거래라는 특성이 추가되나 그 외의 기존 단점을 유사하게 가져갑니다.

 

3) Chaumain e-cash

마지막으로 David Chaum이 제시한 Chaumain e-cash가 존재합니다.

Chaumain e-cash는 아래와 같은 과정으로 거래를 합니다.

 

• e-cash 발행: 사용자가 은행에서 Chaumian e-cash를 구매합니다. 구매 과정에서 블라인드 서명(blind signature) 기술을 사용하여 은행은 사용자의 신원을 알지 못한 채 e-cash를 발행합니다.
• e-cash 보유: 사용자는 발행된 e-cash를 디지털 지갑에 저장합니다.
• 거래 실행: 송신자가 수신자에게 e-cash를 전송합니다.
• 유효성 검증: 수신자는 은행에 e-cash의 유효성을 확인하지만, 은행은 거래 당사자들의 신원을 알 수 없습니다.
• 수신자 수령: 수신자가 유효한 e-cash를 확인하고 이를 자신의 디지털 지갑에 저장합니다.

이 경우 digital Payments, P2P, Privacy, Offline double-spend detection이라는 많은 장점들을 구현할 수 있게 되나,

은행이 Chamian e-cash에 대한 입출금을 거절할 수 있다는 문제를 여전히 가지고 있습니다.

 

그렇다면, 디지털 토큰 거래에 대한 decentralized(탈중앙화된) 를 어떻게 구현할 수 있을까요? 이에 대한 사전 준비가, 바로 해싱과 서명입니다.

 

 

2. 해싱

해시 함수는 간단하지만, 강력합니다.

해시함수는 임의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수입니다.

hash(data) -> output.

이때 data의 size는 어떤 크기여도 가능하며, output의 size는 고정되어 있습니다.

해시 함수의 output은 랜덤처럼 보이나 동일한 input에 대해서는 동일한 output을 뱉기에 랜덤은 아닙니다.

Avalanche Effect는 hash function을 잘 설명하는 효과입니다. 

*Avalanche Effect : 암호학과 해시 함수에서 중요한 특성으로, 입력 데이터가 아주 작은 변화(예: 한 비트 변경)만 있어도 출력값(암호문 또는 해시값)이 완전히 달라지는 현상을 말합니다.

 

해시 함수가 잘 규정되기 위해서는 아래 세 가지의 저항성을 지녀야 합니다.

 - Preimage resistanse (원상 저항성)

주어진 해시값 h에 대해, 이를 생성한 입력값 x를 찾는 것이 계산적으로 불가능해야 한다는 속성입니다.

즉, 해시 함수 H(x)=h에서 h가 주어졌을 때, x를 찾는 것이 매우 어려워야 합니다.

이는 원래 입력값을 역으로 추측할 수 없도록 만드는 속성이며, 해시 함수의 일방향성(one-way property)을 보장합니다.

 

- 2nd preimage resistance (2차 원상 저항성)

preiamge resistance의 확장으로, H(x) = h에서 x를 찾을 수 없음이 주어진 상황에서, x' != x인 ( == x가 아닌)  x'에 대하여 H(x') = h를 찾을 수 없어야 합니다.

 

- Collision Resistance (충돌 저항성)

서로 다른 두 입력값 x1​과 x2​에 대해, 동일한 해시값 H(x1)=H(x2) 을 생성하는 것이 계산적으로 불가능해야 한다는 속성입니다. 즉, 해시 함수가 *충돌(collision)*을 방지해야 합니다. 이는 동일한 해시값을 가지는 서로 다른 입력값을 생성할 수 없도록 보장해주며, 데이터 무결성과 보안성을 강화합니다.

 

일반적으로 잘 만들어진 해시함수는 충돌 저항성에 더 강해야 합니다. 그 이유는 sha-1이나 md5 해시 함수와 같이 기존에 밝혀진 해시 함수의 충돌 문제의 경우 preimage resistance가 온전함에도 collision resistance가 붕괴된 사례이기 때문입니다.

 

이러한 해시들은 특정 정보에 대한 이름, reference, pointer, commit reveal 등에 대한 방식으로 활용할 수 있습니다.

(단, hash를 pointer로 사용하는 경우 cycle한 linked list에 대한 pointer를 구현할 수 없습니다. 이는 preimage resistance에 위배되기 때문)

 

3. 서명 (Signiture)

1)서명의 필수 요건

누군가에게, 본인이 이 메세지를 보냈음을 증명할 수 있는 서명은 3가지의 기능을 요구합니다.

 

-GenerateKeys()

기능:
전자서명을 생성하고 검증하기 위한 *비밀키(secret key)*와 *공개키(public key)*를 생성합니다.

작동 원리:

• 비대칭 암호화 알고리즘(예: RSA, ECDSA)을 사용하여 키 쌍을 생성합니다.
  • 비밀키: 서명을 생성하는 데 사용.
  • 공개키: 서명을 검증하는 데 사용.
• 공개키는 누구나 접근할 수 있도록 공개되며, 비밀키는 서명자만이 보관합니다.

출력:

• secretKey: 서명을 생성하는 데 필요한 개인 키.
• publicKey: 서명을 검증하는 데 필요한 공개 키.

-Sign(secretKey, message)

기능:
주어진 메시지에 대해 **비밀키(secretKey)**를 사용하여 전자서명을 생성합니다.

작동 원리:

1. 메시지를 해시 함수(예: SHA-256)를 사용해 고정된 크기의 해시값으로 변환합니다.
2. 생성된 해시값을 비밀키로 암호화하여 서명을 만듭니다.
3. 결과로 생성된 서명은 메시지가 변경되지 않았음을 보장하며, 비밀키 소유자만 생성할 수 있습니다.

입력:

• secretKey: 비밀키.
• message: 서명할 메시지.

출력:

• signature: 메시지에 대한 전자서명.

---

-Verify(publicKey, message, signature)

기능:
주어진 메시지와 서명이 유효한지 확인합니다. 즉, 서명이 해당 메시지에 대해 올바르게 생성되었고, 메시지가 변경되지 않았음을 검증합니다.

작동 원리:

1. 메시지를 동일한 해시 함수로 해싱하여 해시값을 생성합니다.
2. 서명을 공개키로 복호화하여 서명 생성 시 사용된 해시값을 복구합니다.
3. 복구된 해시값과 메시지의 해시값을 비교합니다.
   • 두 해시값이 일치하면 서명이 유효합니다.
   • 일치하지 않으면 서명이 위조되었거나 메시지가 변경된 것입니다.

입력:

• publicKey: 공개키.
• message: 서명을 검증할 메시지.
• signature: 검증할 서명.

출력:

• Boolean: 서명이 유효하면 True, 그렇지 않으면 False.

2) Lamport Signatures

램포트 서명은 해싱만을 활용하여 만들어 낼 수 있는 서명 방식 중 하나입니다.

램포트 서명은 아래와 같습니다.

 

• 키 생성 - (GenerateKeys())
  • 개인 키(private key):
    길이가 2n인 랜덤한 값의 배열로 구성됩니다. 여기서 n은 메시지의 길이(비트 수)입니다.
  • 공개 키(public key):
    개인 키의 각 요소에 해시 함수를 적용한 결과로 생성됩니다. 즉, 공개 키는 2n개의 해시 값으로 이루어져 있습니다.

Lamport Sig - GenerateKey(), 화살표는 각 바이트 별 해싱을 의미합니다. 강의에서는 256byte를 기준으로 설명합니다.

• 서명 - (Sign(PrivateKey,Message))
  • 서명하려는 메시지를 이진수로 변환합니다.
  • 메시지의 각 비트 값에 따라 개인 키에서 대응되는 값을 선택합니다.
    • 비트가 0이면 개인 키의 첫 번째 값 사용.
    • 비트가 1이면 개인 키의 두 번째 값 사용.
  • 선택된 n개의 값이 서명 값이 됩니다.

메세지 값의 시작이 01101110인 경우, 0에 해당하는 경우 위의 privatekey를 서명값으로 공개하고, 1에 해당하는 경우 아래의 privatekey를 서명값으로 공개합니다.

• 검증 - (Verify(PublicKey,Message,Sign))
  • 서명을 검증하려면 메시지와 서명 값을 이용해 공개 키와 비교합니다.
  • 메시지의 각 비트에 따라 서명 값에 해시 함수를 적용하고, 그 결과가 공개 키의 해당 값과 일치하면 서명이 유효하다고 판단합니다.

Lamport Signiture는 구현하기 쉽다는 장점이 있으나, 동일한 키를 여러번 활용할 수록 privatekey가 점차 공개되기에 일회성에 가깝다는 단점을 가지고 있는 서명 방식입니다.