2023 Advent-of-spin Challenge 2

이 포스트는 advent-of-spin에 업로드 된 Challenge 2에 대해서 진행했던 내용을 정리한 포스트 입니다.

Rust 언어로 진행하였으며 이 포스트에 게시된 소스코드는 Github 에서 확인할 수 있습니다.

Spec

• / 에 POST method 구현하기
  • POST: / body로 아래의 형식대로 값을 전달

       {
           "kids": [1, 4 , 5, 6, 3, 2, 7],
           "weight": [23, 45, 23, 43, 12, 32, 45],
           "capacity": 120
       }
    

  • 결과 값으로 제공된 데이터 세트에 대해서 얼마나 많은 Kids에게 선물을 줄 수 있는지 출력 json { "kids": 18 }
  • response header에 Content-Type: application/json

Work

• 이번 챌린지는 단순하게 POST 메소드로 라우팅을 하나만 뚫으면 되는 간단한 챌린지 입니다.

• spin new 명령어를 이용하여 새로운 프로젝트를 생성해 줍니다.

  

• 그리고 생성된 프로젝트의 Cargo.toml 파일에 아래와 같이 dependencies를 추가해 줍니다.

  

  • request / response 객체를 serialize / deserialize 하기 위해 serde 라이브러리를 사용합니다.
• 이제 구현을 해야합니다.

• 문제를 해결하기 위해서 DP를 사용하여 로직을 구현할 수 있습니다.

    fn optimal_kids_reached(kids: Vec<usize>, weight: Vec<usize>, capacity: usize) -> usize {
        let n = kids.len();
        let mut dp = vec![vec![0; capacity + 1]; n + 1];
      
        for i in 1..=n {
            for w in 1..=capacity {
                if weight[i - 1] <= w {
                    dp[i][w] = dp[i - 1][w].max(kids[i - 1] + dp[i - 1][w - weight[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
      
        dp[n][capacity]
    }
  

• src/lib.rs 에 POST를 처리하기 위한 로직을 구현합니다.

    use http::{Method, StatusCode};
    use serde::{Deserialize, Serialize};
    use spin_sdk::{
        http::{IntoResponse, Response},
        http_component,
    };
      
    #[derive(Debug, Deserialize, Serialize)]
    struct KidsRequest {
        kids: Vec<usize>,
        weight: Vec<usize>,
        capacity: usize,
    }
      
    #[derive(Debug, Deserialize, Serialize)]
    struct KidsResponse {
        kids: usize,
    }
      
    fn optimal_kids_reached(kids: Vec<usize>, weight: Vec<usize>, capacity: usize) -> usize {
        let n = kids.len();
        let mut dp = vec![vec![0; capacity + 1]; n + 1];
      
        for i in 1..=n {
            for w in 1..=capacity {
                if weight[i - 1] <= w {
                    dp[i][w] = dp[i - 1][w].max(kids[i - 1] + dp[i - 1][w - weight[i - 1]]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
      
        dp[n][capacity]
    }
      
    #[http_component]
    fn handle_request(req: http::Request<Vec<u8>>) -> anyhow::Result<impl IntoResponse> {
        let (status, body) = match *req.method() {
            Method::POST => {
                let request: KidsRequest =
                    serde_json::from_slice(req.body().clone().to_vec().as_slice()).unwrap();
      
                let kids = request.kids;
                let weight = request.weight;
                let capacity = request.capacity;
      
                let maximum_kids = optimal_kids_reached(kids, weight, capacity);
      
                let response = KidsResponse { kids: maximum_kids };
      
                let json_response = serde_json::to_string(&response)?;
      
                (StatusCode::OK, json_response)
            }
            _ => (StatusCode::METHOD_NOT_ALLOWED, String::new()),
        };
        Ok(Response::builder()
            .status(status)
            .header("content-type", "application/json")
            .body(body)
            .build())
    }
  

• spin build 로 빌드를 수행합니다.

  

• spin up 으로 로컬에서 실행이 가능합니다.

  

• curl을 사용하여 가볍게 테스트가 가능합니다.

    curl localhost:3000 -H 'Content-Type: application/json' -d '{"kids":[1,4,5,6,3,2,7], "weight":[23,45,23,43,12,32,45], "capacity":120}'
  

  

• 아래 명령어로 제출 전 테스트가 가능합니다.

    hurl --test test.hurl
  

  

2023 Advent-of-spin Challenge 1

이 포스트는 advent-of-spin에 업로드 된 Challenge 1에 대해서 진행했던 내용을 정리한 포스트 입니다.

Rust 언어로 진행하였으며 이 포스트에 게시된 소스코드는 Github 에서 확인할 수 있습니다.

Spec

• /index.html 에 Static page 호스팅 하기 (크리스마스 관련된 무언가를 담아서)
• /data path에서 GET/POST method 구현하기
  • GET /data?advent : 저장된 value값 출력 / 성공시 200
  • POST: /data?advent body에 저장된 값 저장 / 성공시 201

       {
           "value": "<Matt의 자동화된 위시리스트>"
       }
    

  • response header에 Content-Type: application/json

Work

첫번째 요구사항인 /index.html 을 호스팅하기 위해 static-fileserver 을 사용합니다.

생성된 폴더 구조는 아래와 같습니다.

assets 경로에 있는 파일들을 호스팅 해주는 파일서버 입니다.

두번째 요구사항를 위해 key-value store를 만들어줍니다.

이 두 프로젝트를 별도의 서버가 아닌 하나의 서버로 작업할 것이기 때문에 두 프로젝트를 하나로 합칩니다.

합치고 난 이후에 이런 구조가 됩니다.

• component는 key-value store인 spin-key-value와 index.html 을 호스팅해줄 fileserver 총 두가지 컴포넌트가 존재합니다.
• /index.html 경로에 호스팅을 해 주어야 하기 때문에 fileserver 의 route 는 / 로 하였습니다.
• 또한 index.html 만 사용하기 때문에 / 를 /index.html 로 변경하였습니다.
• spin-key-value 의 경우 /data 만이 존재하기 때문에 route를 /data 로 하였습니다.
• key_value_stores = ["default"] 를 spin-key-value 컴포넌트에 추가하였습니다.

이를 실행해보면 다음과 같이 route가 생성됩니다.

이제 구현을 해야합니다.

assets/index.html 경로에 크리스마스 느낌의 이미지가 담긴 html 파일을 만들어줍니다.

<!DOCTYPE html>
<html lang="en">
    <body>
        <img src="https://www.shutterstock.com/image-vector/flork-meme-christmas-vector-ilustration-600nw-2175960549.jpg" />
    </body>
</html>

src/lib.rs 에 GET, POST를 처리하기 위한 로직을 구현합니다.

use http::{Method, StatusCode};
use spin_sdk::{
    http::{IntoResponse, Response},
    http_component,
    key_value::Store,
};

#[http_component]
fn handle_request(req: http::Request<Vec<u8>>) -> anyhow::Result<impl IntoResponse> {
    let store = Store::open_default()?;

    let (status, body) = match *req.method() {
        Method::POST => {
            store.set(req.uri().path(), req.body().as_slice())?;
            println!(
                "Storing value in the KV store with {:?} as the key",
                req.uri().path()
            );
            (StatusCode::CREATED, None)
        }
        Method::GET => match store.get(req.uri().path())? {
            Some(value) => {
                println!("Found value for the key {:?}", req.uri().path());
                (StatusCode::OK, Some(value))
            }
            None => {
                println!("No value found for the key {:?}", req.uri().path());
                (StatusCode::NOT_FOUND, None)
            }
        },
        Method::DELETE => {
            store.delete(req.uri().path())?;
            println!("Delete key {:?}", req.uri().path());
            (StatusCode::OK, None)
        }
        Method::HEAD => {
            let code = if store.exists(req.uri().path())? {
                println!("{:?} key found", req.uri().path());
                StatusCode::OK
            } else {
                println!("{:?} key not found", req.uri().path());
                StatusCode::NOT_FOUND
            };
            (code, None)
        }
        _ => (StatusCode::METHOD_NOT_ALLOWED, None),
    };
    Ok(Response::builder()
        .status(status)
        .header("content-type", "application/json")
        .body(body)
        .build())
}

• spin build 로 빌드를 수행합니다.

  

• spin up 으로 로컬에서 실행이 가능합니다.

  

• curl을 사용하여 가볍게 테스트가 가능합니다.

  • POST

      curl -XPOST http://localhost:3000/data\?advent -H 'Content-Type: application/json' -d '{"value":"todolist
    

    

  • GET

      curl -XGET http://localhost:3000/data\?advent -H 'Content-Type: application/json' -d '{"value":"todolist"}'
    

    

• 아래 명령어로 제출 전 테스트가 가능합니다.

    hurl --test test.hurl
  

  

체인링크 CCIP란?

Chainlink CCIP

Chainlink Cross-Chain Interoperability Protocol (CCIP) 는 EVM 기반 체인에서 Cross-Chain Interoperability를 제공하는 프로토콜 입니다.

체인링크 CCIP는 아래와 같은 기능을 지원합니다.

• Arbitrary Messaging: 임의의 데이터를 다른 네트워크의 Smart contract로 보낼 수 있습니다.

• Token Transfer: 토큰을 다른 네트워크의 Smart contract 혹은 이더리움 주소로 전송할 수 있습니다.

• Programmable Token Transfer: 단일 트랜잭션 내에서 임의 데이터와 토큰을 동시에 전송할 수 있습니다.

Architecture

위 사진은 CCIP의 기본적인 아키텍쳐를 보여줍니다.

Router는 Smart contract 형식으로 구현되어 있으며 아래와 같은 기능을 수행할 수 있습니다.

• 다른 네트워크의 Smart contract transaction을 호출할 수 있습니다.
• 다른 네트워크의 Smart contract 혹은 이더리움 주소로 토큰을 전송할 수 있습니다.
• 동일한 트랜잭션으로 토큰과 임의의 메세지를 함께 보낼 수 있습니다.

Component

Onchain components

Router

Router는 기본 CCIP의 기본적인 smart contract이며 체인당 하나의 Router contract가 존재합니다.

Router contract는 명령을 OnRamp로 라우팅하는 역할을 수행합니다.

Commit store

Committing DON은 CommitStore contract와 상호작용하여 메시지의 Merkle root를 출발지 네트워크에 저장합니다.

Merkle root는 Risk Management Network 에 의해 블레싱(blessing) 되어야 Executing DON이 이를 목적지 네트워크에서 실행할 수 있습니다.

CommitStore은 메시지가 Risk Management Network에 의해서 blessing 되었고 레인(Lane)당 하나씩 존재하는지 체크합니다.

여기서 레인이란 출발지 네트워크와 목적지 네트워크간 경로를 의미합니다. 레인은 단발향이며 A->B 와 B->A는 별개의 레인입니다.

OnRamp

OnRamp contract는 레인당 하나씩 존재합니다. 이 컨트랙트는 아래와 같은 기능을 수행합니다.

• 전송하려는 내용이 목적지 네트워크에 맞는지 검증합니다.

• Message size limit, gas limits을 확인합니다.

• 수신자의 메시지 순서를 보장하기 위해 메시지 순서를 관리합니다.

• 수수료를 관리합니다.

• 메시지에 토큰이 포함되어 있는경우 Token pools와 상호작용 합니다.

• Committing DON이 모니터링 할 수 있도록 이벤트를 내보냅니다.

OffRamp

OffRamp contract는 레인당 하나씩 존재합니다. 이 컨트랙트는 아래와 같은 기능을 수행합니다.

• Executing DON이 제공한 Proof를 사용하여 실제로 메시지가 커밋 되었고, Blessing 되었는지 확인합니다.

• 트랜잭션이 정확하게 한번만 실행 되었는지 확인합니다.

• 검증 이후 수신 된 모든 메시지를 Router로 전송합니다. 이 과정에서 토큰 전송이 포함된 경우 OffRamp는 TokenPool을 호출하여 토큰을 올바른 수신자에게 전송합니다.

Token pools

각각에 토큰은 OnRamp 혹은 OffRamp가 ERC-20에 대한 기능을 원활하게 하기 위한 token pool을 가지고 있습니다.

네이티브 토큰(eg. ETH, MATIC)의 경우엔 해당 기본 체인에서만 발행될 수 있기 때문에 Wrapped Token의 형식으로 목적지 네트워크에서 발행 됩니다.

총 발행량이 고정된 토큰에 경우 Lock and Mint의 방식을 사용하고

일반적으로 총 발행량이 고정되어 있지 않은 토큰에 경우 Burn and Mint의 방식을 사용합니다.

Risk Management Network contract

bless 혹은 curse에 대한 내역을 관리합니다.

OffChain components

Committing DON

Committing DON은 출발지 네트워크와 목적지 네트워크간 트랜잭션을 모니터링하는 작업을 수행합니다.

• 출발지 네트워크에서 OnRamp contract의 이벤트를 모니터링 합니다.

• 출발지 네트워크에서 블록이 finalize 되는것을 기다립니다.

• 트랜잭션을 묶어서 Merkle root를 생성합니다.

• 목적지 네트워크의 CommitStore contract에 Merkle root를 저장힙니다.

Executing DON

Executing DON은 출발지 네트워크와 목적지 네트워크간 트랜잭션을 실행하는 작업을 수행합니다.

• 출발지 네트워크의 OnRamp contract의 이벤트를 모니터링 합니다.

• 트랜잭션이 CommitStore contract에 존재하는 Merkle root의 일부인지 확인합니다.

• Risk Management Network에 의해 메시지가 blessing 될 떄 까지 기다립니다.

• Merkle root에 대하여 유효한 Merkle proof를 만들어 OffRamp contract를 통하여 트랜잭션을 실행합니다.

Risk Management Network

Risk Management Network는 Commitiing DON이 Commit Store에 커밋한 Merkle root를 모니터링하는 독립된 노드 집합입니다.

각 노드는 커밋된 Merkle root를 OnRamp contract에서 받은 트랜잭션과 비교합니다.

검증이 통과 되면 Risk Management Network contract를 이용하여 해당 Merkle root를 bless 합니다.

충분한 blessing이 있으면 해당 Merkle root를 실행할 수 있습니다.

만약 이상이 발생하는 경우 해당 시스템은 curse 합니다.

CRDT에 대해서

Overview

CRDT (Conflict free Replicated Data Types)는 중앙 서버의 개입 없이, 유저 간 컨센서스, 동기화 과정을 거치지 않고도 동일한 상태를 가질 수 있도록 하는 기술입니다.

기존에는 OT (Operational Transformation) 방식을 사용했습니다. 중앙 서버가 유저들의 작업 내용을 모두 받아 이를 적절하게 보정하여 모든 유저들의 상태를 동일하게 하였습니다. 하지만 유저 간 통신으로 동기화가 불가능 하기 때문에 중앙 서버에 과부하가 올 수 있다는 문제점이 있었습니다.

CRDT (Conflict free Replicated Data Types)

CRDT는 두 가지 방식이 존재합니다. State based CRDT(상태 기반 CRDT)와 Operation based CRDT(작업 기반 CRDT) 입니다.

Eventual Consistency

CRDT를 다루기 전에 먼저 Eventual Consistency에 대한 설명이 필요합니다.

Eventual Consistency란 모든 복제본들에 대해서 새로운 상태 업데이트가 발생하지 않을때 동일한 값으로 수렴하는 것이 가능하다는 것입니다.

Eventual Consistency를 만족하기 위해서 아래 3가지 조건이 필요합니다

• Eventual Delivery: 어떤 복제본에 특정 method가 실행 되었다면 다른 복제본에서도 동일한 method가 실행 될 수 있습니다.

• Convergence: 어떤 두 복제본이 동일한 method set을 가지고 수행되었다면 그 두 복제본은 같을 수 있습니다.

• Termination: 모든 method는 정상적으로 실행 되어야 합니다.

Eventual Consistency를 만족하면 CRDT를 만족할 수 있느냐 라고 한다면 그렇지 않을 수 있습니다.

Eventual Consistency 만으로는 동일한 상태를 만들 수 있다는 가능성만을 나타낼 뿐 이를 확실할 순 없습니다.

Strong Eventual Consistency

그래서 조금 더 강력한 조건이 필요합니다. 이를 Strong Eventual Consistency라고 합니다.

Strong Eventual Consistency는 Eventual Consistency에서 업데이트가 다른 순서대로 오더라도 동일한 상태가 된다는 내용입니다.

이를 만족하기 위해서 Eventual Consistency를 만족하면서 아래 조건을 추가로 만족해야 합니다.

• Strong Convergence: 어떤 두 복제본이 동일한 method set을 가지고 수행되었다면 그 두 복제본은 같은 상태를 가집니다.

그래서 CRDT를 달성한다는 것은 SEC를 만족한다는 것과 같은 말이라고 할 수 있습니다.

State based CRDT

State based CRDT는 복제본 간에 상태를 전달하여 모든 복제본의 상태를 일치시키는 방법입니다.

State based CRDT에서 각 복제본은 아래의 튜플을 구성합니다.

$(S, S^0, q, u, m)$

$ S = State, S^0 = Initial \ State$

$ q=Query, u=Update, m=Merge $

Merge function

State의 순서에 상관없이 모든 복제본이 동일한 상태로 수렴하게 하려면 Merge function이 매우 중요합니다.

그러기 위해서 Merge function은 아래의 조건을 만족해야 합니다.

• 교환법칙: 두 상태를 결합할 때 순서를 바꾸더라도 결과 값은 동일하다

• 멱등법칙: 동일한 두 상태를 결합할 때 결합한 상태와 같은 값이 나와야 한다.

• 결합법칙: 3개 이상의 상태에 대해서 결합을 하고자 할 때, 어떤 2개의 상태를 먼저 결합을 하더라도 결과 값은 동일하다.

위의 3가지 조건을 만족하는 Merge function을 구성한다면 State based CRDT를 만족할 수 있게 됩니다.

Operation based CRDT

Operation based CRDT는 복제본 간에 수행된 작업을 전달하여 모든 복제본의 상태를 일치시키는 방법입니다.

State based CRDT에서 각 복제본은 아래의 튜플을 구성합니다.

$(S, S^0, q, u, t m)$

$ S = State, S^0 = Initial \ State$

$ q=Query, t= prepare-update, u=effect-update, m=Merge $

State based CRDT에서 있던 Merge 가 사라지고 Update가 $(u,t)$ 쌍으로 구분 되었습니다.

Commutativity

Operation based CRDT에서도 State based CRDT와 마찬가지로 순서에 상관없이 동일한 상태로 수렴할 수 있어야 합니다.

그러기 위해서 Update 연산에 대해서 순서를 바꾸더라도 동일한 결과값을 획득할 수 있어야 합니다.

위 사진에 보이는것 처럼 $\alpha$, $\beta$ 업데이트를 한다고 했을 때 순서를 바꿔서 업데이트를 수행하더라도 동일한 결과를 얻을 수 있어야 합니다.

이를 만족하는 Update method를 구성한다면 Operation based CRDT를 만족할 수 있게 됩니다.

Sidetree?

이전 포스팅에서 Sidetree protocol에 대해서 다루었는데 Sidetree protocol에서 Sidetree node간 상태를 일치시키는데 CRDT를 사용하고 있습니다.

그러면 Sidetree에서는 State based CRDT를 사용할까요? Operation based CRDT를 사용할까요?

Delta based CRDT

State based CRDT는 모든 복제본에 상태값을 전달하게 되는데 상태값 전체를 전달하게 되면 전송하는 데이터의 사이즈가 굉장히 커질 수 있습니다.

이를 보완하고자 변경 된 상태에 대해서만 다른 복제본으로 전달하는 Delta based CRDT가 파생 되었습니다.

각 복제본은 전체 상태를 다른 복제본으로 전달하지 않고 변경된 상태에 대해서만 다른 복제본으로 전달하게 되고 그 이후 과정은 State based CRDT와 동일하게 수행됩니다.

DID Sidetree 프로토콜

Overview

Sidetree 프로토콜은 탈중앙화 시스템 위에서 DID를 구현할 수 있게 해주는 Layer 2 프로토콜 입니다.

현재 여러 블록체인 위에서 동작하는 많은 DID 시스템이 있지만, 트랜잭션 수수료 및 처리량에 대한 한계가 있기 때문에 그러한 문제점을 해소할 수 있는 방안으로 제시된 프로토콜 입니다.

Network Topology

Sidetree의 네트워크는 크게

• Content Addressable Storage (CAS) (eg. IPFS)
• Sidetree Node
• Decentralized Ledger System (eg. Bitcoin, Ethereum)

의 3가지로 구분될 수 있습니다.

Sidetree Node는 사용자로 부터 특정 요청을 받아 이를 처리합니다. 사용자로부터 받을 수 있는 요청은 DID resolve, 혹은 Create, Update, Recover, Deactivate 등의 동작이 될 수 있습니다.

DID State에 대한 변경이 필요하다면 변경 사항을 Decentralized Ledger System과 CAS에 저장하고 DID State에 대한 조회가 필요하다면 Decentralized Ledger System과 CAS로 부터 필요한 데이터를 불러와 사용자에게 전달 할 것입니다.

DID URI Composition

Sidetree 기반의 DID는 Short-Form, Long-form 2가지로 나뉘어 집니다. Short-form DID는 did:{METHOD}:{DID-SUFFIX} 의 형식으로 이루어져 있으며 Long-form DID는 did:{METHOD}:{DID-SUFFIX}:{LONG-FORM-SUFFIX-DATA} 로 이루어져 있습니다.

Long-Form Suffix Data는 위 사진에 나온 Long-form DID Data를 Base64URL 형식으로 인코딩한 값입니다. 해당 값을 구성하는 필드를 어떻게 생성하는 지는 DID Operation의 Create에서 자세히 설명 할 것입니다.

DID Operation

Sidetree 프로토콜에서 수행할 수 있는 DID Operation은 크게 Create, Update, Recover, Deactivate의 4가지 입니다.

Create

Create Operation은 DID를 생성하는 기능을 수행하며 이후 동작에 사용할 Update Key Pair와 Recovery Key Pair를 생성하는 과정을 포함하고 있습니다.

이 과정에서 Long form DID Data를 구성하는 데이터들을 생성하게 되고 여기서 생성한 값들을 Long-form DID를 구성하는데 사용합니다.

Update

Update Operation은 해당 DID에 대한 attribute를 수정하는 기능을 수행합니다. (eg. add/remove keys, add/remove services, …)

Create Operation 혹은 이전 Update Operation 과정을 수행하면서 만든 Update key를 필요로 하며 동일한 키를 계속 사용하는것이 아닌 새로운 Update key Pair인 Next Update Key Pair를 생성하여 다음 Operation에 사용할 수 있도록 합니다.

Recover

Recover Operation은 해당 DID에 대한 attribute를 복구하는 기능을 수행합니다.

기존에 생성한 Update key, Recovery Key 모두를 필요로 하며 Update와 마찬가지로 이후 Operation에서는 동일한 키를 계속 사용하는것이 아닌 새로운 Update key Pair인 Next Update Key Pair, 새로운 Recovery key Pair인 Next Recovery Key Pair를 생성하여 다음 Operation에 사용할 수 있도록 합니다.

Deactivate

Deactivate는 해당 DID를 비활성화 하는 기능을 수행합니다.

Patches

DID Operation를 수행하면서 Delta Object를 생성하는 과정에서 Patches 라는 필드가 Array로 포함되는데 이 필드에 실제 어떤 기능을 하는지에 대한 내용이 포함됩니다.

Sidetree 프로토콜에서 제공하는 Patches에 대한 종류는 아래 사진과 같습니다.

자세한 내용은 DID State Patches 링크를 참조하세요

Reference

Sidetree DIF spec

ION github