레이블이 deep인 게시물을 표시합니다. 모든 게시물 표시
레이블이 deep인 게시물을 표시합니다. 모든 게시물 표시

[컴][수학] 제곱, 제곱근의 의미

지수, 승수 / 빅오 /



내 멋대로 풀어보는 "제곱근"의 의미

이 이야기는 제곱의 느낌을 위해 log 의 개념을 이용했다고 보면 될 듯 하다.

제곱의 의미가 그렇게 어렵지 않다. 제곱은 곱하기를 몇번 하느냐를 나타낼 뿐이다.

예를 들어 2의 제곱은 2를 2번 곱하는 것이고, 2의 3제곱은 2를 3번 곱하는 것이다.

  • 22  = 2 * 2
  • 23  = 2* 2 * 2
  • ...

그럼 제곱근도 간단하다. 제곱근은 몇번을 곱해야 값이 나오는 가를 알려준다. 

예를 들어 "2의 제곱근"은 "2의 제곱근" 을 2번 곱해야 2가 되는 것이고, "2의 세제곱근"은 "2의 세제곱근"을 3번 곱해야 2가 되는 것이다.(앞으로 제곱근은 편의상 root() 로 표현한다.)

그래서 이 제곱근은 아래 처럼 표현되기도 한다.

그런데 사실 이 제곱근이라는 숫자가 확 와닿지 않는다. 예를 들어 어떤 경우의 수가 10개가 있다라고 했을 때는 금방 이해되지만, 경우의 수가 root(10) 이라고 했을 때는 몇가지를 이야기하는지 잘 와닿지 않는다. 그나마 숫자라면 괜찮지만, 만약 N 이라고 한다면 어떨까?

사람마다 다르겠지만, 내 경우 어떤 값을 뜻하는지 느낌이 잘 안잡혔다. 그래서 이 글을 쓰고 있다.


제곱, 제곱근은 '단계' 이다.

여하튼 서론이 길었는데 결론은 이렇다.

제곱은 단계를 늘리는 것이고, root(N) 는 단계(level)를 줄이는 것으로 이해 하면 된다. 설명이 어렵지만, 일단 그림을 보자

먼저 "제곱"을 보면
  • 22라는 경우라면, 2개의 객체가 자기 자신만큼의 자식을 복제하는 것을 2단계 한 셈이다. 
  • 23라는 경우라면, 2개의 객체가 자기 자신만큼의 자식을 복제하는 것을 3단계 한 셈이다. 
즉 제곱이 한개 올라갈 때 마다, 각 객체가 자가 복제를 한 것이다. 3개도 마찬가지다. (아래 그림 참조.)

반대로 root() 는 단계가 줄어든다.

  • 2의 제곱근은 2단계까지 간 녀석을 1단계로 돌려놓고,
  • 2의 세제곱근은 3단계까지 간 녀석을 1단계로 돌려놓는다.











이제 상상을 하자. 그럼 root(N) 은 무엇일까?
그것은 N 이라는 수가 22나 3같은 숫자인 것이다. 그래서 N은 이미 자기 복제를 해서 2단계로 간 상황이다. 이런 상황에 있는 N을 다시 돌려놓는것이다. 이것이 root(N) 인 것이다.






[컴] 스칼라 곱 - dot product




스칼라 곱


2개의 vector 에 대한 dot product( 스칼라곱 , inner product, scalar product 라고 불린다. ) 는 a ∙ b 로 표현된다.

대수학 정의

그리고 실제 계산은 아래처럼 한다.


기하학적 정의

그런데 이것을 아래처럼 계산하기도 한다.

  • a ∙ b = |a||b| cos(θ) = |b||a|cos(θ)
  • (단 유클리드 공간이며, a, b 는 유클리드 벡터(Euclidean vector) 이다.)

이것은 서로 다른 방향의 벡터를 같은 방향으로 놓고, 그 값(magnitude) 만 계산하려고, A 를 B와 같은 방향으로 만들고, 이것을 곱한 것이라 볼 수 있겠다.





Reference


  1. 스칼라곱 - 위키백과, 우리 모두의 백과사전
  2. Dot product - Wikipedia, the free encyclopedia



[컴] cosine similarity - 코사인 유사도

추천시스템 만드는 법 / 추천 시스템



코사인 유사도

cosine similarity (코사인 유사도) 에 대해 알아보자.

코사인 테이블 을 보면서 이야기를 하자. 코사인은 직각삼각형에서 3개의 각이 있는데 각각의 각(angle) 에 대한 비율을 표시하는 방법으로 sin, cos, tan 라는 이름을 썼다. 그중에 (밑변/빗변) 을 cos(코사인) 이라고 정의했다.

이것을 두개의 벡터(vector) 가 같은 방향(orientation) 을 갖는지 여부를 판별하는 데 사용할 수 있다.

무슨 말인가 하면, 두개의 vector 의 방향이 같다면, 각도는 0도가 되고, cos(0)=1 이 된다. 만약 두개의 vector 의 방향이 90도를 이룬다면, cos(90)=0 이 될 것이다. 만약 vector 의 각도가 180도가 되면 어떨까? 이 때는 -1 이 된다.

정리하면, 두 vector 의 방향이 같으면, 1 이 되고, 점점 각도가 벌어질 수록 값은 작아지고, 결국 90도가 되면 0 이 되는 것이다.

이런 이유로 cos 의 값을 보면 vector 의 방향이 서로 얼마나 다른지를 판단할 수 있게 된다. 이런 식으로 vector 의 방향의 유사성을 판단하는 것을 ‘코사인 유사도’(cosine similarity) 라고 한다.

이런 코사인 유사도는 특히 결과가 "0이상 1이하([0, 1])" 인 positive space(양수공간)에서 많이 쓰인다.



유사도 계산

두 벡터의 스칼라 곱에서 '기하학적 정의' 를 보면 아래와 같이 '스칼라 곱'을 표현할 수 있다.

  • a ∙ b = ||a|| ||b|| cos(θ) 
이 식에서 cos(θ) 를 유도하게 된다. 아래는 ref. 2 에서 가져온 그림이다.
예를 들어 아래와 같은 vector 라면,
  • A = [1, 2]
  • B = [3, 4]
아래처럼 계산되어 진다.



즉, 벡터 A, B 의 유사성(similarity) 는


이 된다.(1 에 가까울 수록 더 유사도가 높다.)



추천 시스템

이것을 이용해서 추천시스템을 만들 수 있다. 추천시스템을 '취향' 이 비슷한 사람을 찾아주는 것이라고 보면 된다.

즉, '취향의 유사도'를 알아내는 것이다.

위와 같이 "한 개인의 취향"을 "한개의 벡터" 로 인식하는 것이다. 여기서 벡터의 구성요소는 각 영화에 대한 '별점' 이 된다.

우리가 흔히 벡터를 표현할 때 아래와 같이 표현한다.

  • vector = [v1, v2, v3..] 

이것은 '여러 방향'을 갖는 '여러 크기'들이 존재하는 것이다. 이런 '여러방향의 여러크기' 를 하나로 묶어서 '벡터' 로 본다.

이것을 '취향' 에 대입을 하면, 개인이 '여러 영화에 대해 매긴 별점' 을 하나로 묶어서 '벡터' 로 보는 것이다.

ref. 5 에서 구체적인 예와 python code 를 확인할 수 있으니 참고하자.



References

  1. Cosine similarity - Wikipedia, the free encyclopedia
  2. 코사인 유사도 - 위키백과, 우리 모두의 백과사전
  3. 삼각함수 공식 총정리 : 네이버 블로그
  4. 벡터(vector)의 길이
  5. Elliot Chance - How to Write Your Own Recommendation System

[컴][파이썬] python 의 Future 가 동작하는 방법




python 3 에서 Future 의 동작 정리


python 3 의 Future 라는 녀석이 있다. 이녀석은 그냥 data 를 나르는 class 정도로 여기면 된다. c 에서 이야기하는 structure 같은 느낌으로 말이다.

그런데 python 의 code 에서 이녀석이 동작하는 방식이 library 안으로 들어가 있어서 언뜻 잘 이해가 안되다.

그래서 동작하는 순서대로 소스를 정리해봤다.


thread 와 future 의 flow


간단한 예제

간단한 아래 예제 소스를 한 번 보자.(출처 : Python: A quick introduction to the concurrent.futures module | Abu Ashraf Masnun)

아래 소스는 간단하다. pool.submit 을 하면 thread 가 만들어지고, thread 가 만들어지면서 future 를 return 해준다. 그러면 thread 가 동작을 하다가 동작을 완료하면 state 를 변경하고, future.set_result() 를 통해 결과를 future 에 넣어준다. 그러면 그 결과를 future.result() 를 통해 가져오게 되는 것이다.

future 를 share 해서 다른 thread 의 결과값을 가져온다고 생각하면 될 것 같다. 자세한 동작은 다음을 보자.

from concurrent.futures import ThreadPoolExecutor
from time import sleep
 
def return_after_5_secs(message):
    sleep(5)
    return message


 
pool = ThreadPoolExecutor(3)
 
future = pool.submit(return_after_5_secs, ("hello"))
print(future.done())
sleep(5)
print(future.done())
print(future.result())



동작

아래 소스를 쭉 따라가보면 최종적으로 _WorkItem.run() 에서 self.future.set_result(result) 를 해서 future 에 result 를 넣어주게 된다.

그래서 우리는 이 future 로 현재 동작하고 있는 thread 의 결과를 쉽게 얻어오게 된다. 이것은 특별한 방법은 아니지만, worker thread 와 main thread 와의 data 전달을 하는 방법을 future 라는 것으로 규격화했다. 그래서 개념만 잘 익힌다면, programming 을 쉽게(?) 할 수 있다.

이런 pattern 이전에 썼던 방법들---queue 를 이용하던지, 아니면 공유되는 variable 을 사용하던지 하는 방법등---을 생각해 보면 이해가 쉬울 듯 하다.


# thread.py

class ThreadPoolExecutor(_base.Executor):
    def __init__(self, max_workers):
        ...
        self._work_queue = queue.Queue()
        ...

    def submit(self, fn, *args, **kwargs):
        with self._shutdown_lock:
            if self._shutdown:
                raise RuntimeError('cannot schedule new futures after shutdown')

            f = _base.Future()
            w = _WorkItem(f, fn, args, kwargs)

            self._work_queue.put(w)
            self._adjust_thread_count()
            return f

    def _adjust_thread_count(self):
        # When the executor gets lost, the weakref callback will wake up
        # the worker threads.
        def weakref_cb(_, q=self._work_queue):
            q.put(None)
        # TODO(bquinlan): Should avoid creating new threads if there are more
        # idle threads than items in the work queue.
        if len(self._threads) < self._max_workers:
            t = threading.Thread(target=_worker,
                                 args=(weakref.ref(self, weakref_cb),
                                       self._work_queue))
            t.daemon = True
            t.start()
            self._threads.add(t)
            _threads_queues[t] = self._work_queue

class _WorkItem(object):
    def __init__(self, future, fn, args, kwargs):
        self.future = future
        self.fn = fn
        self.args = args
        self.kwargs = kwargs

    def run(self):
        if not self.future.set_running_or_notify_cancel():
            return

        try:
            result = self.fn(*self.args, **self.kwargs)
        except BaseException as e:
            self.future.set_exception(e)
        else:
            self.future.set_result(result)

            
def _worker(executor_reference, work_queue):
    try:
        while True:
            work_item = work_queue.get(block=True)
            if work_item is not None:
                work_item.run()
                # Delete references to object. See issue16284
                del work_item
                continue
            executor = executor_reference()
            # Exit if:
            #   - The interpreter is shutting down OR
            #   - The executor that owns the worker has been collected OR
            #   - The executor that owns the worker has been shutdown.
            if _shutdown or executor is None or executor._shutdown:
                # Notice other workers
                work_queue.put(None)
                return
            del executor
    except BaseException:
        _base.LOGGER.critical('Exception in worker', exc_info=True)






# threading.py
class Thread:
    ...
    def __init__(self, group=None, target=None, name=None,
                 args=(), kwargs=None, *, daemon=None):
        ...
        self._target = target
        ...
    def start(self):
        ...
           _start_new_thread(self._bootstrap, ())
        ...
        self._started.wait()

    def _bootstrap(self):
        try:
            self._bootstrap_inner()
        except:
            if self._daemonic and _sys is None:
                return
            raise

    def _bootstrap_inner(self):
        try:
            ...
            try:
                self.run()
            except SystemExit:
                ...

    def run(self):
        try:
            if self._target:
                self._target(*self._args, **self._kwargs)
        finally:
            del self._target, self._args, self._kwargs


# thread.py




[컴][머신러닝] Strategies to scale computationally: bigger data





아래는 6. Strategies to scale computationally: bigger data — scikit-learn 0.17.1 documentation 의 내용을 번역했다.



6.1. Scaling with instances using out-of-core learning


Out-of-core learning 은 RAM 용량보다 더 큰 data 를 통해 learn 할 때 사용하는 기술이다. 대략적으로 아래같은 기술을 사용한다.

  1. instance를 stream 으로 만드는 것
  2. 이 instance 에서 feature 들을 추출(extract) 하는 것
  3. incremental algorithm(점진적인 알고리즘)

6.1.1 Sreaming instances

기본적으로 file들, database, network stream 에서 instance 들을 만들어내는 reader 들일 것이다. 그러나 자세한 이야기는 이 문서의 범위를 넘어간다.

6.1.2. Extracting features

scikit-learn 에 feature 추출을 하는 부분은 구현되어 있다. 하지만 "data 에 대한 vectorization 작업하는 위치"와  "feature 나 값들의 집합이 미리 알려져 있지 않은 부분"에 대해서는 작업을 해줘야 한다.


만약 application 관점에서 data 에 대해 여러개의 pass 들을 만드는 것이 합리적이면 stateful vectorizer 를 사용하는 것은 가능하다.
그렇지 않으면 stateless feature extractor 를 사용해야 하는데 이것이 어렵다. 요즘 선호되는 방식은 hashing trick 이라 불리는 것이다.
scikit-learn 에 구현되어 있는데,

  • sklearn.feature_extraction.FeatureHasher 는 python dicts 들로 이뤄진 list 로 표현된 categorical 변수들의 data set 에 사용할 수 있고,
  • sklearn.feature_extraction.text.HashingVectorizer 는 text documents 에 사용할 수 있다.

6.1.3. Incremental learning

모든 알고리즘이 전체를 파악하지 않고서는 배울 수 없다.
partial_fit API 을 구현한 모든 estimator 들은 후보자들이다.(아래 리스트 참조)

instance 들의 mini-batch 로 부터 점차적으로 배우는 능력(때때로 이것을 online learning 이라 부른다.) 은 out-of-core learning 에서 중요한 부분이다. 알다시피 어떤 주어진 시간에도 메인메모리에 오직 instance 들의 작은 부분만 있는 것만을 보장하기 때문이다.

relevancy 와 메모리 footprint 의 균형을 맞추는 적절한 mini-batch 의 size 를 선택하는 것은 약간의 조율 작업을 필요로할 수 있다.

estimator 리스트

  • Classification
    • sklearn.naive_bayes.MultinomialNB
    • sklearn.naive_bayes.BernoulliNB
    • sklearn.linear_model.Perceptron
    • sklearn.linear_model.SGDClassifier
    • sklearn.linear_model.PassiveAggressiveClassifier
  • Regression
    • sklearn.linear_model.SGDRegressor
    • sklearn.linear_model.PassiveAggressiveRegressor
  • Clustering
    • sklearn.cluster.MiniBatchKMeans
  • Decomposition / feature Extraction
    • sklearn.decomposition.MiniBatchDictionaryLearning
    • sklearn.decomposition.IncrementalPCA
    • sklearn.cluster.MiniBatchKMeans

리스트중에 classification 에 대해서, 약간 언급해야 할 중요한 것은 비록 stateless feature extraction routine 이 새롭거나 보이지 않는 속성(attribute)들을 다룰 수 있을 수 있지만,
점진적인 learner , 그 자체는 새롭거나 보이지 않는 target 들의 class 들을 다룰 수 없을 것이다.
이 경우에 우리는 모든 가능한 class 들을 처음 partial_fit 을 호출할 때 classes parameter 를 통해서 넘겨줄 수 있다.
(역자: stateless feature extraction 으로 새로운 feature 들을 뽑아내는 것은 문제가 없지만, 이 feature 를 어떤 class 로 분류해야 하는데, 이 때 새로운 class 를 알아서 learner 가 만들 수는 없다. 그러므로 이를 위해서 partial_fit 을 처음 call 할 때 classes= 를 통해서 모든 가능한 class 들을 넣어줘야 한다.)

6.1.3. Incremental learning

적절한 알고리즘을 선택할 때 고려해야 할 다른 부분은 모든 알고리즘들이 시간이 지남에 따라 각각의 예제에 대한 중요도가 변한다.

다시말하면, Perception 은 여전히 나쁘게 labeled 된 예제들에 민감하다. 심지어 많은 예제를 처리한 이후에도 그렇다. 반면에 SGD* and PassiveAggressive* family 들이 이런 요소에 좀 덜 민감하다.

반대로, 이후에는 또한 "너무 다름" 에 대해 중요도를 덜 부여하는 경향이 있다. 그렇지만, 시간이 지남에 따라 learning rate 가 감소할 때 stream 의 뒷부분에 적절하게 labeled 된 예제들이 있을때는 그렇지 않다.(해석이 불분명)

[컴][머신러닝] Feature extraction



4.2. Feature extraction — scikit-learn 0.17.1 documentation 의 글 중 일부를 번역해 놓는다.



Feature extraction

Feature extraction 은 text 또는 image 같은 임의의 data(arbitrary data) 를 machine learning 에 쓸수있는 "숫자와 관련된 feature 들(numerical features)"로 변환하는 특징을 갖는다. [ref. 1]


Text feature extraction

The Bag of Words representation

text content 에서 numerical feature 를 추출하기 위해 scikit-learn 에서 다음 3개의 utility 를 제공한다.

  • tokenizing : 이건 문자열을 token 들로 쪼개는 것이다.
  • counting : 각 문서(document) 의 토큰이 몇번 나왔는지를 세는 것
  • normalizing and weighting with diminishing importance tokens that occur in the majority of samples / documents.
tokenizing, counting, nomalizing 을 하는 이 특정 전략을 bag of words 라 한다.

이 전략에서 feature 와 sample 의 정의는 아래와 같다.

  • feature : 여기서 feature 는 "각각의 token의 발생 빈도" 이다.
  • sample : 모든 token 의 빈도들을 갖고 있는 vector 는 다변수의 sample 로 여겨진다.
참고로, text documents 더미를 numerical feature vector 들로 변환하는 것을 vectorization 이라 한다.


"Bag of words" 표현(representation) 또는 "Bag of n-grams" 표현 이라 얘기한다.
여기서 document 는 word 의 occurrence로만 표현된다. 단어의 상대적인 위치 정보는 무시한다.


...

Limitations of the Bag of Words representation

자세한 이야기는 link 를 이용하자. 대략적으로 Bag of words representation 의 한계를 이야기하면, 같은 의미의 단어인데,

  • 철자가 틀렸거나,
  • 복수형등으로 조금 변형된 상태

에서도 다른 단어로 처리하게 되는 것이다. 이런 요소로 classification 의 정확도가 떨어진다. 이런 것을 극복하기 위해 "n-grams" 를 사용하게 된다.

이건 단어 하나를 그대로 하나의 token 으로 인식해서 판별하는 것(n-gam 0)이 아니라, 그것을 여러개의 combination 을 만든다. 예를 들어,
"A T T C A" 라는 문장이 있다면, 이것을 unigram(n-gram 0) 으로 분할 하면,
A, T, T, C, A
로 나눠서 검사를 하는데, bigram(n-gram 1) 로 분할하면,
AT, TT, TC, CA
로 나눠서 이것들을 검사하게 된다.

이렇게 n-gram 을 vectorizer 의 parameter 로 지정해 줄 수 있다. 자세한 것은 link 를 참고하자.



Vectorizing a large text corpus with the hashing trick

이제까지 언급한 vectorization 방법들(CounterVectorizer, TfidfVectorizer 등등) 은 메모리 안에서 token 들을 "정수 feature의 인덱스"에 mapping 했다. 근데 이게 큰 dataset 을 처리할 때 문제가 있다.
  • 더 큰 크기의 문서를 다루면, 많은 더 많은 단어들이 사용되고 이게 또 메모리를 더 많이 사용하게 된다.
  • fitting 은 원본 dataset 에 비례하는 크기의 중간 데이터 구조에 대한 메모리 할당을 필요로 한다.
  • word-mapping 을 만드는 것은 dataset 를 전부 읽는 과정이 필요하다. 그래서 text classifier 를 특히 온라인 등의 환경에 맞우는 것은 불가능하다.
  • 큰 vocabulary_ 를 가지고 vectorizers 를 pickling 과 un-pickling 하는 것은 매우 느릴 수 있다.(일반적으로 같은 크기의 NumPy array 같은 flat data structures 를 pickling / un-pickling 하는 것보다 훨씬 느리다.)
  • vocabulary_ 속성은 공유되는 state 로 하고 "잘 만들어진 동기화 장벽(synchronization barrier)"를 이용해서 vectorization 작업을 concurrent 한 sub task 로 분리하는 것은 쉽지 않다.
    token 문자열 을 feature index 에 mapping 하는 것은 각 token 의 첫 occurrence 의 순서에 달려있다. 그래서 공유되어야만 한다. 그런데 이것은 잠재적으로 councurrent worker들의 sequential variant 보다 더 느리게 만들정도로 성능에 해를 끼친다.


sklearn.feature_extraction.FeatureHasher class 에 구현되어 있는 hashing trick (Feature hashing) 과 CountVectorizer 의 text preprocessing,  tokenization feature 들과 결합해서 이 한계를 극복할 수 있다.


Feature hasing

machine-learning 에서 feature hashing 은 hashing trick 으로 알려져 있다.
빠르고, space 효율적인 feature 를 vetorize 하는 방법이다. 즉, 임의의 feature 들을 vector 안의 index 로 바꿔주는 작업이다.
hash function 를 feature 들에 적용한다. 그리고 그들의 hash 값들이 바로 index 로 이용된다. 중간에 hash 와 array 의 index 를 다시 mapping 하는 부분을 두지 않는다.

보통 document 가 있으면 이것을 word 로 쪼개서 matrix 를 만들게 된다. 그러면 하나의 row 가 하나의 document 를 뜻하게 되고, column 이 한개의 word 를 뜻하게 된다. 이 경우에 word 에 해당하는 index 가 무엇인지를 알려주기 위해 index table 이 필요하다. 일반적으로 learning time 또는 그 전에 training set 의 vocabulary 에 대한 dictionary 를 하나 만들게 된다.


1st doc : Nam is working
2nd doc : Nam is not working

         Nam     is  working   not
1st doc.  1       1     1       0
2nd doc.  1       1     1       1

dictionary = {
 'Nam': 0,
 'is': 1,
 'working': 2,
 'not': 3
}


value = matrix[1][dictionary['Nam']]

 |
 |
 |
 \/
 
value = matrix[1][hashFunc('Nam')]
이것의 문제는 document 크기가 크거나, document 가 많아져서, training set 이 커지고, 그 안의 vocabulary 가 많아지면, dictionary 를 만들기 위해 더 많은 memory 가 필요하다.

이렇게 dictionary 를 만드는 대신에 hashing trick 을 이용하는 feature vectorizer 는 hash function 을 feature(여기선 word 가 되겠다.) 에 적용해서 "미리 정해진 길이의 vector" 를 만들 수 있다.
hash value 를 feature index 로 사용해서 그 index 에 있는 vector 값을 업데이트 한다.(hash value 가 vector size N 을 넘지 않게 하기 위해 mod N 을 해준다.)



이 경우에, collision 이 생길 수 있다. 이를 위해 또 다른 hash function을 제공한다.(그러나 이것으로 collision 이 해결되지는 않을 듯 한데....)



Reference

  1. 4.2. Feature extraction — scikit-learn 0.17.1 documentation
  2. Feature hashing - Wikipedia, the free encyclopedia

[컴] go-ethereum 빌드 하기

이테리움 go 버전 빌드하기 / 에테리움 /



go-ethereum

이녀석이 ref. 1 에 따르면
"Ethereum 의 공식 구현체 중 가장 빠르게 버전업이 되는 구현체이며, DApp 클라이언트 플랫폼으로 Go Ethereum (Geth) 를 공식화" <from ref. 1, ref. 3>
하고 있다고 한다. 여하튼 그래서 이녀석을 택했다.



windows 에서 go-ethereum 설치하기


windows 64 bit 에서 설치하는 법이 나와있다. 여기서는 당연히(?) source compile 부분을 살펴보겠다.

여기서는 winbuild 를 사용해서 compile 하는 방법을 사용한다. (Installation instructions for Windows · ethereum/go-ethereum Wiki · GitHub)


필요한 프로그램

  1. git : Git - Downloads
  2. golang :
    Downloads - The Go Programming Language
    > go1.6.1.windows-amd64.msi 설치
  3. winbuilds 설치 :
    Download and Installation From Windows [Win-builds]
    혹시나 mingw32 가 설치되어 있다면, 지우거나 path 에 드러나지 않게 하자. 여기선 64bit compiler 가 필요하다.(참고)
  4. MinGW-w64 이용 : delve debugger 를 이용할 때 MinGW-w64 가 있어야 해서 MinGW-w64 를 이용하는 것이 winbuilds 를 이용하는 것보다 낫다.(windows 에서 go deubugger delve 설치 를 참고하자.)

위의 3가지가 필요하다.
여기서는 아래 directory 에서 작업을 한다.
  • GOPATH, go-ethereum 설치한 곳 : d:\mine\programming\go\ethereum
  • GOROOT, golang 설치한 곳 : d:\go
  • winbuilds 설치 : d:\winbuilds

빌드 과정

  1. 환경 변수 설정
    set GOROOT=d:\go
    set GOPATH=d:\mine\programming\go\ethereum
    set path=%path%;c:\Program Files (x86)\Git\bin\;%GOPATH%\bin;%GOROOT%\bin;d:\winbuilds\bin\
  2. godep 설치
    d:\go\bin>go get github.com/tools/godep
  3. go-ethereum source 다운로드:
    git clone https://github.com/ethereum/go-ethereum src\github.com\ethereum\go-ethereum
    

  4. 빌드 :
    %GOPATH%\go-ethereum\cmd\geth 로 가서
    git checkout develop && godep go install
  5. 그러면 아래 경로에 geth.exe 가 만들어진다.
    • %GOPATH%\bin\geth.exe
go-ethereum 소스가 약 360 MB 정도 된다.(git 설정파일까지 합해서는 약 450 MB 정도 된다.)





Linux Ubuntu 14.04 에서 빌드

확실히 원래 리눅스 계열에서 작업한 것이라 그런지 리눅스에서 build 하는 것이 간단하다. windows 가 편해서 windows 에서 build 하려고 애썼긴 했는데, 삽질을 줄이려면 vm 깔고, linux 에서 build 하는 것이 훨씬 나은듯 하다.


Go v 1.5.x 설치

apt repository 추가 : Installation Instructions for Ubuntu · ethereum/go-ethereum Wiki · GitHub

sudo add-apt-repository -y ppa:ethereum/ethereum
sudo apt-get update
sudo apt-get install golang
mkdir -p ~/go; echo "export GOPATH=$HOME/go" >> ~/.bashrc
echo "export PATH=$PATH:$HOME/go/bin:/usr/local/go/bin" >> ~/.bashrc

필요한 library 들 설치

sudo apt-get install -y build-essential libgmp3-dev


빌드

git clone https://github.com/ethereum/go-ethereum ~/go/src/github.com/ethereum/go-ethereum
cd ~/go/src/github.com/ethereum/go-ethereum
make geth


최종적으로 geth 파일은 아래 경로에 만들어진다.
  • geth file path : ~/go/src/github.com/ethereum/go-ethereum/build/bin/geth





See Also

  1. How to debug Golang with Visual Sutio Code · Jhinseok Lee
  2. 쿠...sal: [컴] windows 에서 go deubugger delve 설치
  3. 쿠...sal: [컴] go language debugger delve setting + Visual Studio Code




Reference

  1. InsecurePlatformWarning: A true SSLContext object is not available. This prevents urllib3 from configuring SSL appropriately [duplicate]
  2. Good Joon :: Ethereum Repository 설명
  3. Install the Command Line Tools

[컴] Porter / Duff Mode - 1

안드로이드 / 그래픽 포터 더프 모드 / 색 조합 방법 / 그래픽 모드



Porter/Duff Mode

shader 를 사용할 때 모드중에 PorterDuff Mode(Porter/Duff) 가 있다. 오늘은 이녀석에 대해 간략하게 알아보자.

Porter/Duff 는 이 두사람이 쓴 논문에 있는 내용이 2개의 image 를 pixel 정보를 가지고 composite(조합?) 하는 방법에 대해 이야기하는데, 거기에 나온 내용을 구현해 놓은 것이다. 필자도 대충 본 것이라 일단 넘어가자 ^^

ref. 4 를 보면 PorterDuff Mode 의 연산방법에 대한 enum 값이 나와 있다. 근데 공부좀 해야 알아먹을 정도이다. 그래서 여기서는 조금 쉽게 이야기 한다.(대신에 부정확할 수 있지만 그것은 알아서 판단하자.^^;;)

일단 어떤 연산(operator) 이 있는지 알아보자.
  1. DST
  2. DST_ATOP
  3. DST_IN
  4. DST_OUT
  5. DST_OVER
  6. CLEAR
  7. SRC
  8. SRC_ATOP
  9. SRC_IN
  10. SRC_OUT
  11. SRC_OVER
  12. XOR
  13. LIGHTEN
  14. ADD
  15. DARKEN
  16. MULTIPLY
  17. OVERLAY
  18. SCREEN

18개나 있다 ^^;; 오늘은 이중에 설명이 비교적 쉬운(?) 위의 12개에 대해서만 이야기하도록 하자.

설명을 위해서 ref. 2 에서 그림을 좀 가져왔다. 그림을 보면 대략 감이 잡힌다.

from : ref. 2

Porter/Duff formula

Porter / Duff 의 operator 들은 아래 공식을 사용한다. operator 는 모두 아래 공식을 이용하고, s, d , b 에 어떤 값이 들어가느냐에 차이가 있다.
  • Asrc⋅[s]+Adest⋅[d]+Aboth⋅[b]

s, d , b 는 영역을 나타내는 변수라고 보면 된다.
  • source(s) : source 의 영역
  • destination(d) : destination 의 영역
  • both(b) : 겹쳐지는 영역


연산방법들, operators

겹쳐지는 부분

  • SRC_* : "겹쳐지는 부분에서 Source 의 색"을 사용한다.
  • DST_* : "겹쳐지는 부분에서 Dest 의 색"을 사용한다.
  • *_OUT/CLEAR/XOR : 이들은 "겹쳐지는 부분의 alpha 가 0" 이어서 아무런 색도 표현되지 않는다.

겹쳐지지 않는 부위

  • *_ATOP : *에 해당하는 녀석의 alpha 값이 0 + 그 반대에 해당하는 녀석은 자기 색을 갖는다.
  • *_IN : *에 해당하는 녀석의 alpha 값이 0 + 그 반대에 해당하는 녀석의 alpha 값도 0
  • *_OVER : 각자 자기색을 이용한다.
  • *_OUT : * 에 해당하는 녀석은 자기색 + 그 반대에 해당하는 녀석은 alpha 값이 0
  • SRC/DST: * 에 해당하는 녀석은 자기색 + 그 반대에 해당하는 녀석은 alpha 값이 0
예를 들어 DEST_ATOP 이라면, DEST 의 영역들의 alpha 값이 0 이 되는 것이다. 그런데 위에서 겹쳐지는 부분에 대한 정의는 따로 내렸기 때문에 겹쳐지지 않는 영역에 대해서만 적용된다.

이를 표로 나타내면 아래와 같다.

[s] [d] [b]
SRC s 0 s
SRC_ATOP 0 d s
SRC_IN 0 0 s
SRC_OVER s d s
SRC_OUT s d 0
DST 0 d d
DST_ATOP s 0 d
DST_IN 0 0 d
DST_OVER s d d
DST_OUT s d 0
CLEAR 0 0 0
XOR s d 0


일단 대충 여기까지로 이해는 됐을 것 같다. 좀 더 자세한 이야기는 ref. 2 , ref. 5 를 참고하면 된다.


Reference

  1. Fun with Android Shaders and Filters : 안드로이드의 shader/ filter 를 이용하는 법이 예제, 그림과 함께 나와 있다. 예제 소스는 demo sources 에 있다.
  2. Porter/Duff Compositing and Blend Modes – Søren Sandmann Pedersen : Porter/Duff 에 대한 설명이 잘 나와 있다.
  3. Xenomachina: Android's 2D Canvas Rendering Pipeline : 안드로이드의 2D rendering 순서(pipeline)을 다이어그램으로 보여준다.
  4. PorterDuff.Mode | Android Developers
  5. Alpha compositing - Wikipedia, the free encyclopedia



[컴] Android N 에서 좀 더 빨라지는 compiler 에 대한 글



대략적인 요점은 아래에 추출해 놨다. ref. 1 의 글에서 추린 글이다.


Lollipop
use of a compiler known as ‘Quick’,
AOT version of the Dalvik JIT compiler.

ARM and Google are working closely
new ‘Optimizing’ compiler for Android
fully optimized support for ARM’s AArch64 backend

optimizes for both AArch32 and AArch64 (32 and 64-bit) separately

ARM work on AArch64
Google is developing the AArch32 backend.

Unlike Quick, Optimizing
rebuilt from scratch
to produce superior code quality

accomplished by changes to the Intermediate Representation (IR), instead of using two levels IR like in Quick, Optimizing uses just one

improved register allocation
Quick targets speed
results in lots of registers being spilled to the stack

Optimizing
Linear Scan Register Allocation,
slightly slower at compile time
better runtime performance

8 percent increase in compilation speed
10 percent increase in file size
these could be reduced in the future.




Reference


  1. Optimizing Compiler – the evolution of ART | AndroidAuthority

[컴][파이썬] python decorator

python annotation / python anno / python decoration / python decorator


참고 : Python Decorators II: Decorator Arguments

Python decorator 예제

@fixme

# -*- coding: utf-8 -*-

import warning


def fixme(func, *args, **kwargs):
    def new_func(func, self, *args):
        warning.warn("func.__name__" + args[0]



@sync_hitcount : decorator 에 param 이 없는 경우
def sync_hitcount(func):
    """
    Decorator sync_hitcount
    decorator to lock the Remittance update to synchronization
    """
    def lock(token):
        """
        _lock is needed during determinination of the remit status.
        Without it, status could not determined appropriately.
        """
        ret = Remittance.objects.updateHitCount(token)
        if ret['status'] == Remittance.STATUS['done_remit']:
            raise ExpiredRemitException("remit has been done")
        if ret['hit_count'] > 1:
            raise RemitIsLockedException("on remitting")

    def unlock(remitInfo):
        # init hit_count
        remitInfo.hit_count = 0
        remitInfo.save()

    def dec(*args, **kwargs):

        try:
            lock(kwargs['token'])
            func(*args, **kwargs)
        finally:
            unlock(kwargs['remitInfo'])

        return

    return dec

@iframe : : decorator 에 param 이 있는 경우
def iframe(iframe_param):
    def dec(func):
        def dec_dec(*args, **kwargs):
            func(*args, **kwargs)
            return
            
        return dec_dec
    return dec

@iframe : : decorator 에 param 이 있는 경우, class method 에 적용하는 경우
def decorator(iframe_param):
    def dec(func):
        def dec_dec(self, *args, **kwargs):
            func(self, *args, **kwargs)
            return
            
        return dec_dec
    return dec

[컴][그래픽] Bitmap 포맷 정보

비트맵 분석 / 비트맵 정보 / 비트맵 포맷


Bitmap format

1 pixel 의 검은색 bit map(24bit) 에 대한 hex code

42 4D 3A 00 00 00 00 00 00 00 36 00 00 00 28 00
00 00 01 00 00 00 01 00 00 00 01 00 18 00 00 00
00 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00

file size
reserved(not used yet)
file 의 시작위치에서부터 실제data 위치
-----------------
bitmap header size – 각 bitmap variants 마다 size가 다르다. 제공하는 기능이 다르기 때문이다. Windows는 40byte의 size를 쓴다. Bitmap header size 는 지금 이 header size 를 포함해서 40-byte 이다. 즉, 위 그림에서 0x 28 00 00 00 부터 40-byte이다.
width in pixels
height in pixels
-----------------
planes
bits per pixel
compression
-----------------
bitmap data size
hresolution (pixel per meter)
vresolution (pixel per meter)
-----------------
colors
important colors
-----------------
실제 data, 한 pixel 당 3-byte(24bit) 사용.

Bitmap data 분석시



Bitmap 의 저장은 빨간색으로 표시된 왼쪽 아래에서부터 한 줄씩 저장하게 된다.


Null-byte padding

한 line 이 4-byte 로 나누어 떨어지지 않으면, 4의 배수로 맞추기 위해 null-byte를 추가한다.
예를 들면,
가로 5-pixel 의 bitmap 을 24-bit로 저장한다면,
가로줄 하나는
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
이렇게 된다. 이러면 가로줄 하나는 15-byte 가 된다. 그럼 4-byte로 나누어 떨어지지 않는다. 그래서bitmap 으로 저장하게 되면
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 00
이렇게 00(null-byte) 을 붙여서 4-byte로 나누어 떨어지게 한다.
If the number of bytes matching a horizontal line in the image is not divisible by 4, the line is padded with null-bytes.


Reference

  1. http://atlc.sourceforge.net/bmp.html
  2. http://en.wikipedia.org/wiki/Windows_bitmap




[컴][용어] Proof-of-work 란?

일의 증명 / what is proof of work


Proof-of-work 가 무엇일까? bit coin 문서를 보면 proof-of-work 의 이야기가 많이 나온다. 그래서 proof-of-work 에 대한 정의에 대해 살펴보자. 대부분 ref. 1 을 보고 필자가 이해한 바를 정리한 내용이다.



Proof-of-work system

proof-of-work 는 핵심은 비대칭성이다.[ref. 1] 이것은 한쪽은 시간이 오래 걸리고, 다른쪽은 시간이 별로 안걸리는 것을 이야기 한다.

쉬운 예로 어떤 왕이 "저 산을 이쪽에서 저쪽으로 옮겨라"라고 지시했다고 하자. 이 경우에 산을 옮기기 위해 신하들은 엄청나게 오랫동안 일을 하지만, 왕은 산이 옮겨진 것을 확인하는 것으로 간단하게 신하들이 고생했다는 것을 파악할 수 있다.

proof-of-work 에서 client 

proof-of-work 시스템을 번역하면 "일의 증명" 시스템이라고 할 수 있겠다. ref. 1 에서 Proof-of-work 의 예로 CAPTCHA 를 들고 있다. (CAPTCHA 에 대한 설명은 생략한다.)

우리도 이 CAPTCHA 를 가지고 proof-of-work 가 어떤 역할을 하는지 보자.

CAPTCHA 의 대표적인 예로 "이미지로된 영문자"가 있다. CAPTCHA의 "이미지로 된 영문자"는 정상적인 모양이 아니라 조금 비틀어져 있다.

이렇게 조금 비틀어진 이미지로 된 영문자는 컴퓨터의 입장에서 바로 인식할 수 없다. 흔히 이야기하는 image processing 을 해서 비로서 컴퓨터 입장에서 "문자"로 인식한다. 이 분야를 OCR(optical character recognition) 이라 하는데 이 OCR 이라는 것이 그렇게 훌륭하지 않아서 조금만 정자(正字) 에서 벗어나면 인식률이 크게 떨어진다. 결국 이 CAPTCHA 를 컴퓨터가 제대로 읽어드리기 위해서는 이런 비틀어진 이미지에 대한 처리를 해줘야 하는데, 이것은 작업이 빠르게 되지 않는다. 비틀어진 글자들이 어떤 pattern 을 가지고 있는지도 알 수 없으며, pattern 이 없기 때문에 여러가지 경우를 고려해야만 한다. 여하튼 이런 이유로 CAPTCHA 의 글씨는 사람은 빠르게 처리할 수 있지만, 컴퓨터는 시간이 오래걸리게 된다.

만약에 login 과정에 CAPTCHA 를 사용하는 시스템이 있다고 하자. 이 때 만약 누군가가(컴퓨터이든, 사람이든) CAPTCHA 를 통과해서 시스템에 들어오면, 이 통과해서 들어온 녀석은 무조건 login 을 정상적으로 했다고 인정해 준다.

사람이 아닌 컴퓨터가 통과하는 것은 해킹이기 때문에 허락하면 안되는 것 아니냐라고 생각할 수 있다. 하지만 컴퓨터로 통과하려면 이 CAPTCHA 를 처리하는 작업을 하고 들어와야 하는데, 이 CAPTCHA 를 처리하는 시간이,장비나 알고리즘마다 틀릴 수 있지만, 몇시간이상 걸릴 것이다. 이것이 한번의 login 시도만 할 경우에는 해볼만 할 지 모르겠지만, 해커의 입장에서는 비용이 많이 든다. 고작 login 시도 한 번을 위해 몇시간을 투입할 수는 없다. 이것을 병렬로 돌린다고 해도, 여러대의 컴퓨터를 소유해야 하고, 전기도 사용해야 해서 비용 대비 효율이 떨어진다.

즉 "login 시도"를 컴퓨터로 자동화 해도, 원하는 만큼의 속도를 얻기가 힘들다는 이야기다. 보통 컴퓨터로 자동화 하는 이유가 빠르게 여러 번 시도해서 login 을 성공하려는 것인데, 그런 일을 어렵게 한다는 것이다.

이러한 판단을 해커가 하게 된다면, 해커는 굳이 CAPTCHA 를 뚫으려 하지 않는다. 차라리 그 시간에 CAPTCHA 가 없는 곳을 공격하거나, 아니면 사람을 사용해서 일일이 시도하거나, CAPTCHA 를 우회할 방법을 고민할 가능성이 크다.

이렇게 해커에게 이 시스템을 공격하는 것은 돈도, 시간도 많이 드는 작업이라는 것을 알려서, 대부분의 해커가 포기하게 만드는 것이 Proof-of-work 의 목적이다.

proof-of-work 의 server

다시 CAPTCHA 로 돌아가자. server 쪽에서 이 녀석이 CAPTCHA 의 인증을 할 땐 간단히 확인해 줄 수 있다. 자신이 제시한 이미지가 어떤 값을 가지고 있는지 미리 알기 때문에 client 에서 입력한 값과 자신이 입력한 값을 비교해 주기만 하면 된다. 즉 server 는 매우 빠르게 증명해 줄 수 있어서 비용이 거의 들지 않는다.

이래서 server 쪽은 큰 부담없이 CAPTCHA 를 사용할 수 있다.


protocol 종류

이 proof-of-work 의 protocol 에는 2가지 종류가 있다.[ref. 1] 이 protocol 은 ref. 1 의 variants 에 있는 그림을 확인하자.
  1. Challenge-response protocol : CAPTCHA 처럼, 
    1. 요청자(requester)가 문제(challenge) 를 요구하고, 
    2. 제공자(provider)가 문제를 골라서 주면, 
    3. 요청자가 문제를 풀고 수신자에게 주면, 
    4. 수신자가 그 문제를 확인해서 증명하는 방법
  2. Solution-verification protocol : bitcoin 등에서 처럼 요청자가 문제를 요구하는 것이 아니라, 이미 나와 있는 문제들을 푸는 것이다. 이 때 제공자는 어떤 문제를 풀었는지도 확인하고, 답도 확인해야 한다. 이런 scheme 중 하나가 bitcoin 등의 unbounded probabilistic iterative procedures 이다.


비트코인의 작업 증명

  • 실제적으로는 검사하기는 쉬우나, 풀어내기는 어려운 것을 PoW라 한다.
  • 이것을 이용해서 bitcoin 에서는 하나의 어려운 문제에 대한 해답을 얻으면(CPU 능력을 소모) , 블록체인 원장(ledger)에 새로운 block을 더할 수 있도록 한다.
  • 네트워크안의 모든 node(컴퓨터들)가 문제를 풀게 된다.
  • 이 때 가장 빨리 풀어낸 node 가 코인으로 보상을 받게 된다. 이과정을 채굴(mining) 이라고 한다.
  • 이것이 consensus mechanism 이 된다. 즉, 이녀석이 많은 작업증명을 해결했다는 것은 곧 CPU 자원을 가장많이 사용한 녀석이기 때문에 이녀석의 ledger 를 채용한다는 동의를 해준다.(컨센서스 알고리즘 참고 자료 :  Raft 알고리즘)
  • 이렇게 cpu 의 소모가 많아서 쉽게 조작하지 못한다. 대체로 악의적인 유저가 cpu 를 소모해서 ledger의 내용을 고치는 것보다는 mining 을 하는 것이 cpu 소모가 적다. 이것이 blockchain 이 pow 를 이용하는 이유 중 하나다.



Reference

  1. Proof-of-work system - Wikipedia, the free encyclopedia
  2. 창시자의 무더기 트윗이 의미하는 이더리움 블록체인의 미래 - CIO Korea, 2018.08.23

[컴] 비트코인 논문 번역 및 정리

비트코인 / blockchain /  bitcoin / 블록체인 / 


conan's lazy blogging : 비트코인의 원리



1. Introduction

거래 발생시간순서의 증거(이 증거는 계산을 요구한다.)를 만들어내기 위해 p2p 분산 timestamp server 를 이용하는데, 이를 이용해서 우리는 이중으로 사용하는 문제에 대한 해결책을 제시한다.
정직한 node 들이 다른 협력적인 공격 node 들의 그룹보다 좀 더 많은 CPU 파워를 집합적으로 통제하는 한, 이 시스템은 안전하다.

 we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions.
The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.



2. Transactions

전자코인을 "디지털서명의 연결(chain)"로 정의한다.
(역자: 여기서 이야기하는 transaction 이 block 안에 들어가는 transaction 들중 한개를 이야기하는 것이다.)

owner 는 자신의 코인을 다음 주인(next owner) 에게 전달하기 위해
"이전 거래(previous transaction)의 값 + 다음 주인(next owner)의 public key" 의 hash 를 얻고
이것을 디지털방법으로 서명(sign)한다.
그리고 이 것을 코인의 끝에 더한다.
  • digital signing(hash(previous trans. + next owner's public key))



문제는 지불받는 사람(payee) 이 주인중 하나가 중복해서 이 코인을 사용하지 않았다는 것을 증명할 수 없다는 것이다.(double-spend)

이것에 대한 일반적인 해결책이 중복사용(double-spend) 를 방지하기 위해 모든 거래를 검사하는 "신뢰할 수 있는 중앙기관"(trusted central authority) 이나 "조폐국"(mint) 를 도입하는 것이다.

각 거래후에 코인은 새로운 코인을 발행하기 위해서 조폐국(mint)에게 돌아가야만 한다. 그리고 조폐국이 직접발행한 코인만이 중복사용(double spent)이 안되었다고 신뢰할 수 있다.

이 해결책의 문제는 전체의 화폐시스템이 화폐를 주조하는 회사에 의존한다는 것이다. 모든 거래가 그 회사를 통해야만 한다. 마치 은행처럼 말이다.

지불받는 사람(payee)이 이전의 주인들(previous owners) 이 다른 이전의 거래들에 사인하지 않았다는 것을 알기위한 방법이 필요하다.(중복 사용하지 않았다는 것을 알 방법이 필요하다.)

이것을 위해서, 가장 빠른 거래(the earliest transaction)가 세는 주체다.(one that counts) 그래서 우리는 이후의 중복사용(double spend)의 시도들을 신경쓰지 않는다.(코인의 맨처음 거래가 거래들을 세기 시작한다. 가장 빠른 시점의 거래부터 세기 시작하니, 뒤에 중복사용은 들킨다?)

거래가 빠졌다는 것(absence of a transaction)을 확신하는 유일한 방법은 모든 거래를 아는 것이다.

조폐국 모델에서는, 조폐국이 모든 거래를 알고 있고, 어느쪽에 먼저 도착할지를 결정했다.

신뢰성있는 집단(trusted party)없이 이것을 달성하기 위해서, 거래들은 공개적으로 알려져야 한다.(publicly announced)
(역자: the earliest transaction 이 순서를 count 하고, 이 count 를 공개적으로 알려서 신뢰를 얻는다?)

그리고 우리는 참가자들이 그들이 수신받은 기록에 대한 "하나의 순서 기록"(single history of order in which they were received) 에 동의하기 위한 시스템이 필요하다.(참가자들이 받은 수신기록들이 어떤 순서로 이루어진 것인지 알 수 있어야 한다.)




3. Timestamp Server

우리가 제안하는 해결책은 timestamp server (날짜 도장 서버)로 시작한다.

timestamp server 는 "날짜도장이 찍힐 item 들에 대한 block" 의 hash 를 취한다.(그림)
그리고 넓게 그 hash 를 배포한다.(publishing the hash) .마치 신문 또는 Usenet post 처럼 말이다.

<역자: 위의 그림은 2개의 input 이 들어가서 한개의 hash 값을 만드는 것을 보여준다. 2개의 input 중 한개는 이전의 hash 이고, 다른 하나는 block 이다.>

날짜도장(timestamp) 은 그 시각에 그 data 가 틀림없이 존재하고 있는 상태라는 것을 증명한다. 그 data 가 hash 에 들어가기 위해(in order to get into the hash) 존재했기에, hash 가 만들어질 수 있었던 것이니 말이다.

각 날짜도장(timestamp) 는 그들의 hash 에 이전의 날짜도장(previous timestamp) 을 포함한다. 이런 방법을 이용하면 날짜도장(timestamp) 들로 이뤄진 chain 을 형성하게 된다. 이런 chain 이 형성되기 때문에 새로운 날짜도장(timestamp) 이 들어오면, 이전의 chain 에 추가되는 모습이 된다. 즉 chain 이 계속 늘어나게 된다.


4. Proof-of-Work

분산 timestamp server(날짜도장서버, 날짜도장 서비스를 해주는 무엇) 를 p2p 기반에서 구현하기 위해 Proof-of-Work 를 사용할 필요가 있다. 이 Proof-of-work 는 신문이나 Usenet post들 보단 Adam Back의 Hashcash 와 비슷한 Proof-of-Work 시스템을 사용할 필요가 있다.
(여러 곳에서 동시에 timestamp 가 생길테니 이것들을 너무 쉽게 만들어 내지 못하도록, 그래서 어떤 일을 했다는 것에 대한 증명을 하기 위해, 하지만 만들어진 것의 증명은 쉬어야 하기에,  Proof-of-Work 가 필요?)
(즉, 작업하는데에 어느정도 시간이 들어가야 한다.? timestamp server의 작업이 쉬운일이 아니라 부하를 줘서 어려운 일로 만들어서 이것을 모든 참가자들이 동의하는 하나의 history 로서 역할하게 하기 위해 진입장벽을 높여야 한다.?)

Proof-of-Work(일의 증명) 는 SHA-256등의 hash 함수로 hash 된 값 중에 n 개의 0 bit 로 시작하는 녀석을 찾는 것(scanning)을 포함한다.

필요한 0 bit 의 수가 늘어날 수록, 필요한 "평균적인 일의양" (the average work required)은 기하급수적(exponential ) 으로 늘어난다. 이것은 한개의 hash 를 수행하는 것으로 증명되어 질 수 있다.(간단히 증명된다. 즉, 찾아낸 값을 input 으로 hash function 을 돌리면 바로 hash 값을 알 수 있고, 이 hash 값이 몇개의 '0' bit 로 시작하는지 확인하면 된다.)

우리의 timestamp 네트워크에서, 우리는 block 의 hash 값이 "필요한 수의 0 bit" 를 갖게 되는 순간까지 block 의 nonce를 증가시키는 것으로 "proof-of-work" 를 구현한다.
(Proof-of-work_system : client 쪽에서 시간이 걸리는 작업을 해서 자신을 증명할 수 있는 무엇인가를 server 로 보내고 서버는 간단히 그것이 증명됐다는 것을 판단할 수 있게 해주는 것?, 이것을 통해서 mining 등은 어렵지만, 그렇게 만들어진 block 을 다른 node 들이 검사할 때는 간단하게 할 수 있다. proof-of-work란? )

"CPU 노력(CPU effort)"이 proof-of-work 를 만족시키기 위해 "CPU 노력"이 쓰여진 상태가 된 이후에는, 그 block 은 다시 그 작업을 하지 않고서는 변경되어질 수 없다.
나중 block들(later blocks) 이 그 block에 연결되면(chained after it) , 그 block 을 변경하는 작업은 그 뒤에 연결된 모든 block 들을 재작업해야만 한다.

proof-of-work 는 또한 다수결에서 대표를 결정하는 문제를 해결해 준다.

만약에 다수가 "1개의 IP 주소"가 "1 표"를 의미한다고 하면, 그것은 많은 IP 주소를 할당 받은 어떤 사람이 그 체제를 전복시킬 수 있다는 이야기가 된다.

Proof-of-work 는 근본적으로 "1개의 CPU" 가 "1표"를 의미한다.

다수는 가장 긴 연결(the longest chain) 에 의해 나타내어진다.(가장 긴 연결이 다수이다.) 이 가장 긴 연결은 그것에 투자된 가장 큰 proof-of-work 노력을 했다는 이야기가 된다.(the greatest proof-of-work effort)

(역자: 즉, 긴 연결일 수록 '0' bit 로 시작하는 hash 값을 더 많이 찾아야 한다. 더구나 이 hash 값을 찾는 것은 갈수록 어려워진다. 그러므로 가장 긴 녀석이 가장 많은 노력을 기울였다고 할 수 있다.)

만약 CPU 의 대다수가 정직한 node들에 의해 조정된다면, 이 정직한 연결(chain) 은 가장 빠르게 커지고(grow), 다른 경쟁하는 연결들을 앞설 것이다.

(역자 : 여기를 보고, 이해한 바는 이렇다. 만약 2곳에서 동시에 block 을 만들어서 퍼뜨렸다고 할 때 더 빠르게 퍼진쪽의 block 이 최종적으로 받아드려질 가능성이 높다. 왜냐하면, 더 많은 노드가 있다는 것은 새로운 block 을 추가할 가능성이 더 높다는 것을 의미한다. 어차피 한시간당 평균 block 수는 어느정도 일정하다. 그렇다면, 많은 node 가 자신이 만든 block 을 가지고 있을 때 자신의 block 을 가지고 그 다음 block 을 만들 가능성이 높아진다. 어느 한 순간에 만들어지는 block 수는 일정하다면, 그 "block 을 만드는 node" 가 될 가능성은 당연히 node 의 수가 많을 수록 확률이 높다. 그렇게 되면 더 많은 노드가 내가 만든 block 을 기초로 연결(chain) 을 확장했다는 뜻이되고, 최종적으로 내가 만든 block 을 기초로 만든 연결(chain) 이 가장긴 연결(the longest chain) 이 될 가능성이 크다는 뜻이 된다. 그뜻은 곧 내 block 이 받아드려질 가능성이 높다는 이야기가 된다.)

과거 block 을 수정하기 위해서, 공격자는 그 block 과 그 block 이후에 연결된 block 들에 대한 proof-of-work 를 다시 해야만 한다. 그리고 나서 정직한 node들의 work 를 따라잡고, 그리고 정직한 node 의 work 보다 많이 일해야 한다.(surpass)
(역자: 즉, 누군가가 현재있는 history 를 조작해서 자신이 사용한 내역을 없애거나, 또는 추가하거나 등의 작업을 할려고 한다면, 과거 block 을 조작하거나, 현재 새로 만들어질 block 에 그 내용을 추가하거나 해야 한다. 일단 과거 block 을 조작하는 일은 조작한 block 이후의 block 에 대한 proof-of-work 를 해야만 하기에 거의 불가능하다.)

우리는 이따 좀 더 느린 공격자들이 따라 잡을 가능성이 block 들이 추가될 수록 기하급수적으로 줄어드는 것을 보여줄 것이다.

증가하는 하드웨어 속도를 감안하고 작업시간에 따른 이익을 다양화 하기 위해서 proof-of-work 의 난이도(difficulty) 는 "움직이는 평균"(moving average)에 의해 결정된다. 이 움직이는 평균은 한시간당 평균 block 수를 목표로 한다.

만약 proof-of-work 가 너무 빠르게 만들어 진다면, 난이도(difficulty) 는 증가한다.


5. Network

네트워크를 운영하기 위한 단계들은 아래와 같다.
  1. 새로운 거래들(transactions)이 모든 node 들에 알려진다.(broadcast)
  2. 각 노드는 새로운 거래들을 한개의 block 으로 모은다.
  3. 각 노드는 그 block 에 대한 "어려운 proof-of-work"(difficult proof-of-work) 를 찾기위해 일한다.
  4. 노드가 proof-of-work 를 찾으면, 그 노드가 그 block 을 모든 node 에게 알린다.
  5. 그 block 안에 있는 모든 거래들이 유효하고(valid) 이미 사용(spent)되지 않은 것일 때만 노드들이 그 block 을 받아 드린다.(역자: 각node 가 자신이 가지고 있는 block 과 같은 block 에 대한 proof-of-work 인 것을 확인한다?)
  6. 노드들은 그 block 을 받아 드리게 되면 그들이 그 block 을 받아드렸다고 표현한다.(express) 그 표현은 연결(chain) 에서 자신들이 받아드린 그 block 의 hash 를 previous hash 로 사용해서 다음 block 을 만드는 것을 작업하는 것으로 한다.

노드들은 언제나 가장 긴 연결(the longest chain)을 올바른 것(correct one) 이라고 인식한다. 그리고 노드들은 계속해서 그 연결(chain) 을 확장한다.
만약에 2개의 노드가 동시에 다른 버전의 "다음 block"을 퍼뜨리면(broadcast) , 어떤 노드들은 둘 중 하나를 먼저 받게 될 것이다.
이 경우에, 그들은 그들이 먼저 받은 녀석을 가지고 작업을 할 것이다. 하지만 다른 branch 가 더 길어지는 경우를 대비해서 저장해 놓는다.
이런 tie(무승부) 는 다음 proof-of-work 를 찾게되고 한개의 branch 가 길어지면 깨진다.

새로운 거래(transaction) 를 퍼뜨리는 것은 꼭 모든 노드들에게 닿을 필요는 없다.(새로운 거래가 모든 노드들에게 퍼뜨려지지 않아도 된다.)
그들이 많은 노드들에 닿는한, 그들은 오래지 않아 블럭에 포함될 것이다. 블럭 퍼뜨림(block broadcasts) 들은 또한 dropped message 에 잘 견딜 수 있다.(tolerant of dropped messages)
만약 노드가 block 을 수신하지 못하면, 노드는 다음 block 을 받고 한개를 miss 했다는 것을 인지할 때 그 block 을 요청할 것이다.

(이 글 참고하면 이해하는 데에 도움을 줄 것이다.)


6. Incentives

관습적으로 block에 있는 첫번째 거래(transaction) 은 특별하다.
이 첫번째 거래는 block의 창조자가 소유한 "새로운 코인"을 시작한다.
이 첫번째 거래(transaction) 는 노드를 위해 인센티브(incentive) 를 더해준다. 이 인센티브가 있어서 노드들은 네트워크를 지원하게 되고, 코인이 처음에 유통 (circulation) 되는 상황으로 배포시키는 방법을 제공한다.
아시다시피 그것을 발행하는 중앙기관이 없기때문에.
(Bitcoin Fees | Bitcoin Transaction Fees Explained 에는 25 XBT 가 새로운 코인을 만들면 생긴다고 한다. 이것이 210,000 block 이 생길 때 마다 반감된다. 대신에 transaction fee 를 더 많이 챙기게 돼서 이것을 상쇄한다고 이야기 한다. 그런데 거래비용(transaction fee) 를 부과하는 것은 자유라서, 못받을 수 있다.)


 일정한 양의 새로운 코인이 꾸준히 추가되는 것은 금을 캐는 광부가 금을 유통(circulation) 시키기 위해 자원을 쓰는 것과 같다. 우리의 경우에, 쓰여지는 것은 "CPU 시간"과 "전기"이다.

인센티브는 거래 비용(transaction fee)을 이용해서 자금이 제공되어 진다.
만약에 거래의 결과 값(output)이 입력값(input)보다 작으면, 그 차이가 "그 거래을 포함하는 block" 에 대한 인센티브에 더해진 거래비용(transaction fee) 이 된다.
(하지만 TX fees aren't mandatory 라는 글에 따르면, 거래비용을 주는 것이 의무적인 사항은 아니기 때문에 거래에 거래비용을 추가하지 않을 수 있지만, 이 경우에 새로운 block 을 만드는 miner 가 거래비용이 없는 거래를 block 에 추가하는 데에 오래 걸리게 될 것이고, 영영 추가하지 않을 수도 있다. 이것은 즉 그 거래가 승인되지 않음을 뜻한다. Bitcoin Fees | Bitcoin Transaction Fees Explained)


미리 정해진 수의 코인이 유통에 들어간 상태가 되자마자, 그 코인에 붙어있는 그 인센티브는 거래비용(transaction fee) 으로 완전히 변경 될 수 있다.(transition entirely) 그리고 이때 전혀 인플레이션이 없다.
(역자: 새롭게 통화가 늘어났으니, inflation 이 발생할 수 있다. 하지만, 가치도 함께 더해져서 그 시장에는 가치가 많아졌고, 그 가치에 대한 통화가 발행됐으니 인플레이션이 없다?)

인센티브는 아마 노드들이 정직하게 머무는 것을 장려할 것이다. 만약 탐욕적인 공격자가 모든 정직한 노드들보다 좀 더 큰 CPU power 를 만들 수 있다면, 그는 2가지 선택중 하나를 선택해야 한다. 하나는 그의 지불을 다시 빼내오는 방법으로 사람들을 속여서 빼앗는데(defraud) 사용할 것이고, 다른 하나는 새로운 코인을 만드는 데에 사용하는 것이다.

그는 그 시스템과 그가 가진 부의 타당성을 약화시키는 것 보다는 규칙들을 따라서 play 하는 것이 좀 더 이익이라는 것을 알아야 할 것이다.(ought to)  이 규칙들이 그에게 다른 사람들이 가지고 있는 코인을 합한 것보다 더 많은 새로운 코인을 준다.(이 bitcoin 의 규칙이 그렇게 큰 CPU power 가 있다면, 규칙을 따라서 작업했을 때 다른 사람을 속이는 것보다, 그냥 새로운 코인을 만드는 것이 더 이득이 되게 되어 있다.? 코인을 만들때 거래비용이 있는transaction 을 많이 포함해서 만들 수록 더 큰 금액을 얻을 수 있다면, 그 방법이 더 빠르다.?)




7. Reclaiming Disk Space


코인에 있는 최근의 거래(transaction)가 충분한 block 들 아래로 묻히자마자, 그 이전에 사용된 거래(spent transaction) 은 disk 공간을 절약하기 위해 버려질 수 있다.

block 의 hash 를 파괴하지 않고 이것을 이용하기 위해서, 거래들(transactions)은, 오직 그 블럭의 hash 를 만들때 사용된 root hash와 함께, Merkle Tree 형태로 hashed 되어야 한다.

그리고나서 오래된 blocks 들은 그 tree 의 branch 들을 뽑아 없애는 것을 통해서(stub off) 작게 되어질 수 있다.(compacted)
(이것은 Merkle Tree 의 모습이다. Merkle Tree 는 대체로 binary tree 로 되어 있는데, 자체가 각각의 node leaf 를 hash 하고, 이 hash 된 값들을 모아서 다시 hash 하는 형식으로 단계적으로 hash 를 계속해 나간다. 이렇게 되면, 하나의 tree 안의 작은 tree 들도 각각 독립된 Merkle Tree 의 모습이 된다. 즉, root hash 가 맞다면 이 tree 전체가 맞는 값이 된다. 이런 형식이라서 그 이전의 값이 필요없다. 자세한것은 wikipedia 를 참고하자.)

내부의 hash 들은 저장할 필요가 없다.

거래(transaction) 들이 없는 block 헤더는 약 80 bytes 정도이다. 만약에 블럭들이 매 10분마다 만들어진다고 가정하면, 1년에 약 4.2 MB 정도가 된다.(80bytes * 6 * 24 * 365 = 4.2MB )
2008년에 일반적으로 팔리는 컴퓨터 시스템들은 일반적으로 2.4 GB 의 RAM 을 가지고 있고, Moore's Law(무어의 법칙, 2년에 약 2배로 증가) 으로 계산해 보면 1년에 1.2GB 정도의 성장을 예상할 수 있다.
그러므로 심지어 block header 들이 memory 에 저장된다고 해도 저장공간(storage) 문제가 되지 않을 것이다.



8. Simplified Payment Verification

지불(payment)들을 증명하는 것은 모든 네트워크 노드에서 증명하지 않아도 가능하다.

유저는 "가장 긴 proof-of-work 연결(chain) 의 block" 의  header 의 복사본을 유지하는 것이 필요하다. "가장 긴 proof-of-work 연결(chain) 의 block" 의  header 는 그가 가장 긴 연결(longest chain) 을 가지고 있다고 확신할 때까지 네트워크 노드들에게 질문을 해서 얻을 수 있다.

그리고 그 거래(transaction) 를 날짜도장이 찍힌 그 block (the block it has timestamped in) 에 연결하는 Merkle branch 를 얻는 것이 필요하다.

그는 거래를 그 스스로 점검할 수 없다. 그러나 그 거래(transaction)를 연결(chain)에 있는 어떤 지점으로 연결하는 것으로 그는 네트워크 노드가 그것을 받아드렸다는 것을 확인 할 수 있다.
그리고 그 이후로 더욱 추가된 block 들이 그 네트워크가 그것을 받아드렸다는 것을 확인해준다.

 그렇기 때문에, 정직한 노드들이 네트워크를 컨트롤하는 한은 그 증명(verificaiton) 은 신뢰할 수 있다.  하지만 만약 그 네트워크가 공격자에게 압도당하면 그 증명은 더욱 취약하다.

네트워크 노드들이 스스로 거래들을 증명할 수 있는 반면에, 이 간단화된 방법은, 공격자가 네트워크를 계속해서 압도하고 있는 동안에는 공격자의 가상 거래들(fabricated transactions)에 의해 속을 수 있다.

이것을 막는 한가지 전략은 노드들이 유효하지 않은 block 을 발견했을 때 그들로 부터 경고(alert)를 받고, 사용자의 소프트웨어가 full block과 경고가 발생한 거래(alerted transaction)들을 다운로드 하는 것을 촉진하는 것이다. full block 과 alerted transactions 을 받아서 불일치(inconsistency) 하는 것을 확인할 수 있다.

빈번히 돈을 받는 비지니스들은 아마도 여전히 좀 더 독립적인 보안과 빠른 증명을 위해서 그들의 노드들을 운영하기를 원할 것이다.


9. Combining and Splitting Value

코인들을 각각 다루는 것이 가능하지만, transfer 에서 모든 cent 에 대해 각각의 거래(separate transaction) 로 다루는 것은 힘들다.

가치(value) 가 분리되고, 다시 합쳐지는 것을 가능하게 하기 위해, 거래들(transactions) 은 여러가지 input 들과 output 들을 포함한다.
일반적으로 더 큰 이전의 거래(transaction) 으로 부터 온 한개의 input 이나 또는 더 작은 양들을 묶은 여러개의 input 들 이 있을 것이다.
그리고 많아야 2개의 output 이 있다.
하나는 지불, 또 하나는 보낸자(sender)에게 돌아가는 거스름돈(change) 이다.
한개의 거래(transaction) 가 여러개의 거래들(transactions) 로 이루어진 곳,
그리고 더 많은 것으로 이루어진 거래들(transactions) 에게 팬아웃(fan-out: 전자회로에서 output 에 연결 가능한 input 의 수)은 문제가 아니다.
(output 에 연결가능한 input 의 수의 제한 등은 없으니, 그냥 마음껏 연결해도 된다.라는 것 같다.)

거래 history 의 완전한 독립적인 복사본(complete standalone copy of a transaction's history) 을 추출할 필요는 전혀 없다.



10. Privacy


전통적인 은행 모델은 정보에 대한 접근을 "관여된 집단"과 "믿을 수 있는 제3의 집단"으로 제한해서 프라이버시의 레벨을 달성한다.

공개적으로 모든 거래를 알리는 것의 필요성은 이 방법을 사용하는 것을 불가능하게 한다.(preclude)
그러나 다른 장소에서 정보의 흐름을 차단하는 것(public key 들을 익명으로 보관하는 것에 의해 )으로 프라이버시는 여전히 유지될 수 있다.

대중은 누군가가 다른 누군가에게 보내는 것을 볼 수 있지만, 누구에게도 그 거래(transaction) 에 연결(linking)되는 정보가 없다.

이것은 증권거래소에서 제공되는 정보의 레벨과 비슷하다. 증권거래소에서는 그 집단이 누구인지 안알려주고, 개개의 거래들의 시간과 규모를 나타내는 테이프(tape) 가 공개된다.

추가적인 방화벽으로서, 거래가 공통의 owner 에 연결(link)되는 것을 막기위해, 각각의 거래(transaction) 에 new key pair 가 사용되어져야 한다.

몇몇 multi-input 거래들(transactions) 에서 연결(linking)은 여전히 어쩔 수 없다.
multi-input 거래들은 그들의 input 들이 같은 주인에 의해 소유됐었다는 것이 필연적으로 노출된다.
이것의 위험은 만약 키의 주인(owner)이 노출되면, 연결(linking) 은 같은 주인에게 속한 다른 거래들(transactions) 을 노출 시킬 수 있다.



11. Calculations


우리는 공격자가 다른 연결(chain) 을 정직한 연결(honest chain) 보다 더 빠르게 만들기위해 노력하는 시나리오를 고려한다.

심지어 이것이 달성된다고 하더라도, 그것은 시스템에서 난데없이(out of thin air) 새롭게 가치(value) 를 만들거나 공격자의 소유가 아닌 돈을 가져가는 등의 임의적인 변경이 가능하지는 않다.(역자: 2.Transaction 을 보면, 돈의 소유가 변경되려면 이전의 소유자(previous owner)가 sign 을 해줘야 한다. 이것이 불가능하기에 공격자가 가져갈 수 없는 듯 하다.)

노드들은 가치없는 거래(transactions) 을 payment 로 받아들이지 않는다.
그리고 정직한 노드들은 그것을 포함한 블럭을 받아드리지 않을 것이다.(never accept)
공격자는 단지 그가 가진 거래중에서 그가 최근에 사용한 돈을 다시 가져오기 위해서만 거래를 변경하려고 시도할 것이다.










<참고>





See Also



비트코인 원본 논문: http://bitcoin.org/bitcoin.pdf



[컴][웹] JWT, Json Web Token 이 무엇일까?

JWT 에 대해서 알아보자. / JWT 동작 원리




JWT, Json Web Token

Json Web Token  이다. 인증등을 위한 json 형식의 token 이라고 보면 된다. 대략적인 예제와 이야기는 아래글에서 파악하자.


훔쳐가되, 조작은 못한다.

필자가 파악한 이녀석의 의도는 OAuth 등의 목적과 비슷하다.
api 등을 사용하는데 필요한 key (token) 을 훔쳐가서 쓸 수는 있지만, 너희들이 이 key 를 만들어서 쓰거나, 훔친 key 를 조작할 수는 없을 것이다.
라는 전제를 깔고 있다. 그리고 이 전제는 기본적으로 web 상에서 훔침을 당하는 행위를 방지 할 수 없다는 뜻도 내포한다고 본다.


OAuth 1.0a 와 차이

ref. 2 에 따르면 이 JWT 도 OAuth 2.0 spec 안에 들어가는 듯 하다. 그러므로 아래 이야기는 OAuth 1.0 과의 차이로 생각하고 보도록 하자.

기존의 OAuth 와 비교해 본다면 결국 좀 더 자세한 정보를 전달할 수 있다는 점이 차이일 것이다. 그래서 OAuth 의 비해서 JWT 이 얻는 이득은 아래와 같다. (위 목록의 Using JSON Web Tokens as API Keys 를 참고하자.)
  • OAuth 는 인증이 됐다는 의미만을 가지고, 그 token 자체에 어떠한 의미를 전달할 수 없다. 이 때문에 단편적인 정보만을 전달한다. 하지만 JWT 를 이용해서는 json 형식의 token 을 전달하기 때문에 json 으로 의미있는 내용을 전달할 수 있다. 예를 들면 auth level 같은 것들 말이다.
  • 이로 인해 또 한가지 expire time 을 정해줄 수 있다. OAuth 는 이러한 것들이 불가능하다고 할 수는 없지만, 한 번 token 을 생성하고 일정시간 후에 expired 한다는 개념보다는 한 번 만들어 놓고 계속 사용하는 개념이 강하다.(개인적인 생각이다.)
  • 그리고 OAuth 는 만들어 놓은 token 을 DB 등에 저장해 놓고, 비교하는 형식이지만, 이녀석은 그렇지 않다고 한다. 로그인의 세션처럼 그때 그때 만들어 사용하는 개념인 듯 하다.


여기까지는 필자가 위의 글을 읽고 파악한 JWT 의 특징이라고 하겠다. 어디까지나 개인적인 생각이다.


JWT 의 동작 및 구현

여하튼 여기서 얘기하고자 하는 것은 이런 분석이 아니라, 실질적으로 JWT 가 어떻게 구현된 건지에 대해 정리하려 한다. 대부분의 내용은 아래 글의 내용이다.

JWT 만들기

JWT 는 아래와 같은 모양으로 되어 있다.
JWT Header Segment.JWT Payload Segment.JWT Crypto Segment
아래와 같은 모양으로 되는 것은 JWT Compact Serialization 을 사용한 결과다. 또다른 Serialization 이 있는데, 이녀석을 이용하면 좀 더 다른 모양이 된다. 여기를 참고하자.

위의 JWT 에 대해 좀 더 자세히 이야기 해 보자.
JWT Header Segment.JWT Payload Segment.JWT Crypto Segment
여기서 JWT Payload segment 에는 JWT Claims 가 들어간다. 각각의 segment 는 아래 처럼 생겼다. JWT Crypto 는 "JWT Header + '.' + JWT Claims" 를 input 으로 해서 encryption 한 값이 된다.


JWT Header
{"typ":"JWT",
 "alg":"HS256"}
의 UTF-8 를 Base64url 로 encoding 한 값
eyJ0eXAiOiJKV1QiLA0KICJhbGciOiJIUzI1NiJ9


JWT Claims
{"iss":"joe",
 "exp":1300819380,
 "http://example.com/is_root":true}
의 UTF-8 를 Base64url 로 encoding 한 값
eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ


JWT Crypto
alg(JWT Header + '.' + JWT Claims)
eyJ0eXAiOiJKV1QiLA0KICJhbGciOiJIUzI1NiJ9.eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ
이 값의 UTF-8 을 이용해서 JWT Header의 algo 에 쓰여진 알고리즘으로 encryption 한다. 그리고 이렇게 나온 값을 다시 Base64url 로 encoding 한다. 그래서 아래처럼 나왔다고 가정하자.
dBjftJeZ4CVP-mB92K27uhbUJU1p1r_wW1gFWFOEjXk

그러면 최종적인 JWT 는 아래와 같은 모양이 된다.(JWT Compact Serializer 를 사용했을 때)
eyJ0eXAiOiJKV1QiLA0KICJhbGciOiJIUzI1NiJ9.eyJpc3MiOiJqb2UiLA0KICJleHAiOjEzMDA4MTkzODAsDQogImh0dHA6Ly9leGFtcGxlLmNvbS9pc19yb290Ijp0cnVlfQ.dBjftJeZ4CVP-mB92K27uhbUJU1p1r_wW1gFWFOEjXk


Validation

먼저 JWT Header, JWT Claims 는 JSON 형식이 맞는지를 확인하고, JWT Crypto 는 JWT Header, JWT Claims 를 이용해서 다시 만들어 보는 것으로 validate 를 한다.

이렇게 3개가 전부 validated 되면, JWT 가 괜찮다고 여기는 것이다. 이 사이트에서 확인 해 볼 수 있다.


어디에 실어 나를까?

이부분은 마음대로 해도 되는 듯 하다. http header 에 넣어서 사용해도 되고, 단순히 GET, POST 의 parameter 로 넘겨도 되는 듯 하다. 관련해서 parameter 가 더 작은 byte 를 소모한다는 내용의 글이 있으니 참고하자.



해킹에 대한 대비

이런 모양의 token 이라 결국 중간에서 token 을 steal 당할 수는 있다. 하지만 expired 기간을 짧게 가져가서 steal 당한 이후의 피해를 줄이는 방법으로 가야 하는 듯 하다.
expiration 에 대한 예는 아래 글을 확인하자.


See Also


  1. Django REST framework JWT



Reference

  1. JSON Web Token (JWT) - Claims and Signing
  2. OAuth 2.0 - Open API 인증을 위한 만능 도구상자 - tebica story



[컴][보안] 패스워드 보안 - password hash function

패스워드 해쉬 함수 /


password hash function

패스워드 관련 암호화 자료를 찾다가 좋은 자료를 찾았다. 아래에 password hash function 과 관련된 전반적이고 자세한 이야기, 이슈등을 정리해서 잘 알려주고 있다.



결론

결론적으로 위의 글에서 추천하는 방법은 아래 2가지 이다.

  1. bcrypt
  2. PBKDF2 

안드로이드에서 PBKDF2 사용




Asymmetric  < symmetric

Asymmetric 암호화보다는 symmetric 암호화가 훨씬 secure 하다고 한다.




[컴][알고리즘] liked list 에 cycle이 존재하는 지 판단 하는 방법

자바 알고리즘 / 링크드 리스트에 loop / linked list 에 loop 이 있는지 판단하는 방법 / circular linked list



liked list 에 cycle이 존재하는 지 판단 하는 방법

linked list 가 있을 때 이 linked list 가 loop 인지(즉, cycle) 아닌지를 판단하는 방법에 대한 알고리즘을 ref. 1 에서 설명하고 있다.

개인적으로는 내가 지나온 길을 기억하고 있다가, 내가 간 길이 지나온 길과 같으면 있다고 판단하려 했는데, 이 방법은 확실히 큰 linked list 에서 memory 가 많이 필요하게 된다.

ref. 1 에서는 훨씬 간단한 방법을 채용하고 있다. 방법은 이해하고 나면 쉽다. 이 방법을 이해하는데에는 역시 비유가 좋을 듯 하다.

토끼와 거북이가 운동장 트랙을 계속해서 도는 모습을 상상하면 된다. 그러면 둘의 속력이 다르기 때문에 둘은 언젠가 만난다. 이것을 코드로 옮긴 것이 ref. 1 이다.

만약 토끼가 어딘가 막다른 곳에 다다른다면, 그것은 운동장 트랙이 cycle 이 아니라는 이야기가 된다. cycle 이라면 계속해서 몇바퀴를 돌 게 될 테고, 결국 거북이를 만날테니까 말이다.

그래서 "토끼" 는 2개씩 node를 jump 해서 움직이고, "거북이" 는 1개씩 node 를 움직이다.

실질적인 코드는 ref. 1 을 확인하자.

Reference

  1. How to Find if Linked List contains Loops or Cycles in Java - Coding Question

[컴][안드로이드] Volley 분석

안드로이드 볼리 / 안드로이드 volley 분석 / analyze the volley with source code / volley 소스 분석


Contents

  1. Sequence Diagram
  2. RequestQueue
    1. RequestQueue.add()
  3. CacheDispatcher 와 NetworkDispatcher
    1. CacheDispatcher
    2. NetworkDispatcher
  4. ResponseDelivery
  5. Reference



Sequence Diagram


먼저 위의 diagram 으로 대략적인 동작을 파악하면 이해가 좀 더 잘 되지 않을까 싶다. 위의 diagram 은 "새창에서 열기/새탭에서 열기" 등을 통해 열자. 그래야 크게 보여준다.

diagram 은 detail 한 동작에 대한 내용은 없으니 자세한 사항은 code 를 확인하자.




RequestQueue

RequestQueue 를 new 하면 
  • ExecutorDelivery 
를 만들고, start() 하게 되면, 
  • 1개의 cacheDispatcher + 여러개의 networkDispatcher
를 만든다.


// Activity.kt
mQueue = MyVolleyRequestQueue.getInstance(this.getApplicationContext())!!.getRequestQueue()

mButton!!.setOnClickListener(object : View.OnClickListener {
   public override fun onClick(v: View) {
       mQueue!!.add(jsonRequest)
   }
})


// MyVolleyRequestQueue.kt
public class MyVolleyRequestQueue private constructor(context: Context) {
    private var mRequestQueue: RequestQueue? = null
    private var mCtx: Context


    init {
        mCtx = context
        mRequestQueue = getRequestQueue()
    }

    public fun getRequestQueue(): RequestQueue? {
        if (mRequestQueue == null) {
            val cache = DiskBasedCache(mCtx.getCacheDir(), 10 * 1024 * 1024)
            val network = BasicNetwork(HurlStack())
            mRequestQueue = RequestQueue(cache, network)
            // Don't forget to start the volley request queue
            mRequestQueue!!.start()
        }
        return mRequestQueue
    }
    ...
}




// RequestQueue.java
public RequestQueue(Cache cache, Network network, int threadPoolSize,
            ResponseDelivery delivery) {
    mCache = cache;
    mNetwork = network;
    mDispatchers = new NetworkDispatcher[threadPoolSize];
    mDelivery = delivery;
}

public RequestQueue(Cache cache, Network network, int threadPoolSize) {
    this(cache, network, threadPoolSize,
            new ExecutorDelivery(new Handler(Looper.getMainLooper())));
}


// ExecutorDelivery.java
public class ExecutorDelivery implements ResponseDelivery {
    /** Used for posting responses, typically to the main thread. */
    private final Executor mResponsePoster;

    /**
     * Creates a new response delivery interface.
     * @param handler {@link Handler} to post responses on
     */
    public ExecutorDelivery(final Handler handler) {
        // Make an Executor that just wraps the handler.
        mResponsePoster = new Executor() {
            @Override
            public void execute(Runnable command) {
                handler.post(command);
            }
        };
    }
    ...
}



// RequestQueue.java
/**
 * Starts the dispatchers in this queue.
 */
public void start() {
    stop();  // Make sure any currently running dispatchers are stopped.
    // Create the cache dispatcher and start it.
    mCacheDispatcher = new CacheDispatcher(mCacheQueue, mNetworkQueue, mCache, mDelivery);
    mCacheDispatcher.start();

    // Create network dispatchers (and corresponding threads) up to the pool size.
    for (int i = 0; i < mDispatchers.length; i++) {
        NetworkDispatcher networkDispatcher = new NetworkDispatcher(mNetworkQueue, mNetwork,
                mCache, mDelivery);
        mDispatchers[i] = networkDispatcher;
        networkDispatcher.start();
    }
}


public class RequestQueue {
 ...
 /** The cache triage queue. */
    private final PriorityBlockingQueue<Request<?>> mCacheQueue =
        new PriorityBlockingQueue<Request<?>>();

    /** The queue of requests that are actually going out to the network. */
    private final PriorityBlockingQueue<Request<?>> mNetworkQueue =
        new PriorityBlockingQueue<Request<?>>();
    ...
}

 



ReqeustQueue.add()

request queue 는 내가 원하는 request 를 RequestQueue 에 add 하는 것으로 일이 처리되기 시작한다. 나름의 시작지점이라고 할 수 있다. 이 add() 의 동작은 아래와 같다.

  1. 먼저 request 를 사용하기 전에 mCurrentRequests 라는 Set에 넣어놓고, 현재 처리하고 있는 녀석이라는 것을 알 수 있게 해놓는다.
  2. request 가 caching 을 하지 않아도 된다면, network dispatcher 에게 처리해 달라고 하기 위해 바로 network queue 로 보낸다.
  3. caching 이 필요한 경우라면 일단 이미 들어왔던 요청중에 cache dispatcher 나 network dispatcher 로 request 를 보낸 상황인지를 check 하기 위해 mWaitingRequests 라는 Map을 가지고 있다. 여기에 들어가 있으면 이미 들어왔던 요청이라는 것으로 생각한다.
  4. 그래서 처음에는 mWaitingRequests 에 없을 테니, 이 request를 cache dispatcher 에게 처리해 달라고 하기 위해 mCacheQueue 로 보낸다. 그리고 이 request 를 mWaitingRequests 에 넣어놓는다.
  5. request 가 이미 처리되고 있는 상황이라면, stagedRequests 로 처리하게 된다. 이부분은 아직 의미파악이 안돼서 일단 넘어가자.





// ReuqestQueue.java
/**
 * Adds a Request to the dispatch queue.
 * @param request The request to service
 * @return The passed-in request
 */
public <T> Request<T> add(Request<T> request) {
    // Tag the request as belonging to this queue and add it to the set of current requests.
    request.setRequestQueue(this);
    synchronized (mCurrentRequests) {
        mCurrentRequests.add(request);
    }

    // Process requests in the order they are added.
    request.setSequence(getSequenceNumber());
    request.addMarker("add-to-queue");

    // If the request is uncacheable, skip the cache queue and go straight to the network.
    if (!request.shouldCache()) {
        mNetworkQueue.add(request);
        return request;
    }

    // Insert request into stage if there's already a request with the same cache key in flight.
    synchronized (mWaitingRequests) {
        String cacheKey = request.getCacheKey();
        if (mWaitingRequests.containsKey(cacheKey)) {
            // There is already a request in flight. Queue up.
            Queue<Request<?>> stagedRequests = mWaitingRequests.get(cacheKey);
            if (stagedRequests == null) {
                stagedRequests = new LinkedList<Request<?>>();
            }
            stagedRequests.add(request);
            mWaitingRequests.put(cacheKey, stagedRequests);
            if (VolleyLog.DEBUG) {
                VolleyLog.v("Request for cacheKey=%s is in flight, putting on hold.", cacheKey);
            }
        } else {
            // Insert 'null' queue for this cacheKey, indicating there is now a request in
            // flight.
            mWaitingRequests.put(cacheKey, null);
            mCacheQueue.add(request);
        }
        return request;
    }
}


CacheDispatcher 와 NetworkDispatcher

위에서도 보듯이 RequestQueue.start() 를 통해 CacheDispatcher, NetworkDispatcher 를 생성하게 된다. 그리고 이 만들어진 dispatcher 들은 RequestQueue.add() 를 통해 보내진 request 를 처리하는데에 사용된다.

이 2개의 Dispatcher 의 동작을 대략적으로 정리하면 아래와 같다.
  • CacheDispatcher : 캐쉬 queue에서 queue 에서 요청을 가져와서 처리한다. 이 요청에 대해 cache 에서 찾아보고 있으면 찾은 녀석을 mDelivery 를 통해 보내고, 없으면 network request 를 하도록 network queue 로 보낸다. 
  • NetworkDispatcher : 네트워크 queue 에서 요청을 가져와서 처리한다. 이 요청에 대해 network request 를 보내고 response 를 받는다. 이 response 를 cache 에 넣은 후에 mDelivery 를 통해 전단한다.

아래 코드에서 보듯이 Thread 로 되어 있으며, 이들은 각자 무슨 일을 하고 있다. 이제 무슨 일을 하는지 좀 더 자세히 알아보도록 하자.

// CacheDispatcher.java
public class CacheDispatcher extends Thread {
 /** The queue of requests coming in for triage. */
    private final BlockingQueue<Request<?>> mCacheQueue;

    /** The queue of requests going out to the network. */
    private final BlockingQueue<Request<?>> mNetworkQueue;

    /** The cache to read from. */
    private final Cache mCache;

    /** For posting responses. */
    private final ResponseDelivery mDelivery;

    /** Used for telling us to die. */
    private volatile boolean mQuit = false;

    /**
     * Creates a new cache triage dispatcher thread.  You must call {@link #start()}
     * in order to begin processing.
     *
     * @param cacheQueue Queue of incoming requests for triage
     * @param networkQueue Queue to post requests that require network to
     * @param cache Cache interface to use for resolution
     * @param delivery Delivery interface to use for posting responses
     */
    public CacheDispatcher(
            BlockingQueue<Request<?>> cacheQueue, BlockingQueue<Request<?>> networkQueue,
            Cache cache, ResponseDelivery delivery) {
        mCacheQueue = cacheQueue;
        mNetworkQueue = networkQueue;
        mCache = cache;
        mDelivery = delivery;
    }
    ...
}

// NetworkDispatcher.java
public class NetworkDispatcher extends Thread {
    /** The queue of requests to service. */
    private final BlockingQueue<Request<?>> mQueue;
    /** The network interface for processing requests. */
    private final Network mNetwork;
    /** The cache to write to. */
    private final Cache mCache;
    /** For posting responses and errors. */
    private final ResponseDelivery mDelivery;
    /** Used for telling us to die. */
    private volatile boolean mQuit = false;

    /**
     * Creates a new network dispatcher thread.  You must call {@link #start()}
     * in order to begin processing.
     *
     * @param queue Queue of incoming requests for triage
     * @param network Network interface to use for performing requests
     * @param cache Cache interface to use for writing responses to cache
     * @param delivery Delivery interface to use for posting responses
     */
    public NetworkDispatcher(BlockingQueue<Request<?>> queue,
            Network network, Cache cache,
            ResponseDelivery delivery) {
        mQueue = queue;
        mNetwork = network;
        mCache = cache;
        mDelivery = delivery;
    }
    ...
}



CacheDispatcher

CacheDispatcher 의 하는 일을 알아보기위해 run() 을 살펴보자. Dispatcher 는 InterruptedException 을 받기 전까지는 계속 살아있는 상태로 유지된다. 그래서 while(true) 로 무한 loop 을 돌고 있다.

이 loop 를 돌기 전에 mCache.initialize() 로 자신이 사용할 cache 를 초기화 시켜 놓는다.

그후에 아래와 같은 대략적인 작업들을 하게 된다.
  1. cache queue 에서 request 를 하나 가져온다.(mCacheQueue.take())
  2. 그 request 가 cancel 된 것인지 확인하고 cancel 됐으면, request.finish() 를 호출하고 1 번 작업을 다시 진행한다.
  3. cancel 이 되지 않은 request 에서 cache key 를 가져오고, 이 key 로 mCache 에서 해당하는 entry 가 있는지 찾아본다.
  4. key 에 해당하는 entry 가 없다면, 이 request 를 network queue 로 보낸다.
  5. key 에 해당하는 entry 가 있다면, 이 녀석이 expired 된 녀석인지를 확인하고, expired 됐으면 이 request 를 network queue 에 보낸다.
  6. 이제 mCache 에서 찾은 entry 가 사용할 수 있는 녀석이 라는 것을 확인했다.(cache-hit) 이제 이녀석을 사용하면 되는데, 이 entry 를 그냥사용하진 않고, 이 entry 를 이용해서 response 를 만들어 사용한다.
  7. 이렇게 response 를 만든 이후에 한가지 확인을 더하는데 그것이 softTTL 이라는 녀석이다. 이 softTTL 이 만료되면, 이 entry 를 사용하긴 하는데, 나중을 위해서 update 를 해놓는다.( entry.refreshNeeded() )[ref. 2]
    개인적인 생각에 이것은 미리 가져와서 최대한 cache 에서 data 를 가져오기 위한 정책인 듯 하다.
  8. 사용할 수 있는 entry 는 mDelivery.postResponse(request, response); 를 이용해서 delivery 한다.



public class CacheDispatcher extends Thread {

    ...

    @Override
    public void run() {
        if (DEBUG) VolleyLog.v("start new dispatcher");
        Process.setThreadPriority(Process.THREAD_PRIORITY_BACKGROUND);

        // Make a blocking call to initialize the cache.
        mCache.initialize();

        while (true) {
            try {
                // Get a request from the cache triage queue, blocking until
                // at least one is available.
                final Request<?> request = mCacheQueue.take();
                request.addMarker("cache-queue-take");

                // If the request has been canceled, don't bother dispatching it.
                if (request.isCanceled()) {
                    request.finish("cache-discard-canceled");
                    continue;
                }

                // Attempt to retrieve this item from cache.
                Cache.Entry entry = mCache.get(request.getCacheKey());
                if (entry == null) {
                    request.addMarker("cache-miss");
                    // Cache miss; send off to the network dispatcher.
                    mNetworkQueue.put(request);
                    continue;
                }

                // If it is completely expired, just send it to the network.
                if (entry.isExpired()) {
                    request.addMarker("cache-hit-expired");
                    request.setCacheEntry(entry);
                    mNetworkQueue.put(request);
                    continue;
                }

                // We have a cache hit; parse its data for delivery back to the request.
                request.addMarker("cache-hit");
                Response<?> response = request.parseNetworkResponse(
                        new NetworkResponse(entry.data, entry.responseHeaders));
                request.addMarker("cache-hit-parsed");

                if (!entry.refreshNeeded()) {
                    // Completely unexpired cache hit. Just deliver the response.
                    mDelivery.postResponse(request, response);
                } else {
                    // Soft-expired cache hit. We can deliver the cached response,
                    // but we need to also send the request to the network for
                    // refreshing.
                    request.addMarker("cache-hit-refresh-needed");
                    request.setCacheEntry(entry);

                    // Mark the response as intermediate.
                    response.intermediate = true;

                    // Post the intermediate response back to the user and have
                    // the delivery then forward the request along to the network.
                    mDelivery.postResponse(request, response, new Runnable() {
                        @Override
                        public void run() {
                            try {
                                mNetworkQueue.put(request);
                            } catch (InterruptedException e) {
                                // Not much we can do about this.
                            }
                        }
                    });
                }

            } catch (InterruptedException e) {
                // We may have been interrupted because it was time to quit.
                if (mQuit) {
                    return;
                }
                continue;
            }
        }
    }
}




NetworkDispatcher

이녀석도 계속 loop 을 돌면서 일을 처리한다. 그런데 InterruptException 에 의한 quit 은 queue 에서 request 를 받아올 때에만 정상적으로 종료되고, 나머지 경우에는 다른 error 와 같이 처리되고, mDelivery 를 통해서 전달된다.

그 후 작업은 아래와 같다.
  1. request 가 cancel 됐는지를 살펴본다.
  2. request 가 cancel 됐으면 request.finish() 를 실행한다.
  3. mNetwork.performRequest(request) 를 통해 network 통신을 해서 response 를 가져온다.
  4. network 로 request 를 보내고 돌아온 응답이 304(not modified) 인 경우이고, response 가 delivered 됐다면, 굳이 현재 response 를 건내줄 필요가 없다.(이 녀석은 soft ttl 과 같이 보면 될 듯 하다.) 그래서 response 를 끝낸다.(response.finish())
  5. request 가 cache 되어야 하는 녀석으로 되어 있고, response 의 cacheEntry 가 null 이 아닌 경우에 mCache 에 response.cacheEntry 를 넣어놓는다.
  6. request 가 delivered 됐다고 표시하고(request.markDelivered())
  7. response 를 보낸다. mDelivery.postResponse(request, response)



public class NetworkDispatcher extends Thread {
    ...

    @Override
    public void run() {
        Process.setThreadPriority(Process.THREAD_PRIORITY_BACKGROUND);
        Request<?> request;
        while (true) {
            long startTimeMs = SystemClock.elapsedRealtime();
            // release previous request object to avoid leaking request object when mQueue is drained.
            request = null;
            try {
                // Take a request from the queue.
                request = mQueue.take();
            } catch (InterruptedException e) {
                // We may have been interrupted because it was time to quit.
                if (mQuit) {
                    return;
                }
                continue;
            }

            try {
                request.addMarker("network-queue-take");

                // If the request was cancelled already, do not perform the
                // network request.
                if (request.isCanceled()) {
                    request.finish("network-discard-cancelled");
                    continue;
                }

                addTrafficStatsTag(request);

                // Perform the network request.
                NetworkResponse networkResponse = mNetwork.performRequest(request);
                request.addMarker("network-http-complete");

                // If the server returned 304 AND we delivered a response already,
                // we're done -- don't deliver a second identical response.
                if (networkResponse.notModified && request.hasHadResponseDelivered()) {
                    request.finish("not-modified");
                    continue;
                }

                // Parse the response here on the worker thread.
                Response<?> response = request.parseNetworkResponse(networkResponse);
                request.addMarker("network-parse-complete");

                // Write to cache if applicable.
                // TODO: Only update cache metadata instead of entire record for 304s.
                if (request.shouldCache() && response.cacheEntry != null) {
                    mCache.put(request.getCacheKey(), response.cacheEntry);
                    request.addMarker("network-cache-written");
                }

                // Post the response back.
                request.markDelivered();
                mDelivery.postResponse(request, response);
            } catch (VolleyError volleyError) {
                volleyError.setNetworkTimeMs(SystemClock.elapsedRealtime() - startTimeMs);
                parseAndDeliverNetworkError(request, volleyError);
            } catch (Exception e) {
                VolleyLog.e(e, "Unhandled exception %s", e.toString());
                VolleyError volleyError = new VolleyError(e);
                volleyError.setNetworkTimeMs(SystemClock.elapsedRealtime() - startTimeMs);
                mDelivery.postError(request, volleyError);
            }
        }
    }

    private void parseAndDeliverNetworkError(Request<?> request, VolleyError error) {
        error = request.parseNetworkError(error);
        mDelivery.postError(request, error);
    }
}



ResponseDelivery

ResponseDelivery#postResponse 에서 하는 일은 많지 않다.

일단 request 가 deliver 됐다고 표시 해 준다.(request.markDelivered())
그리고 UI thread 에서 할 일이 몇 개 있는 데 그 일들을 UI thread 로 전달 해 준다.

UI thread 로 넘어와서 하는 일은 아래와 같다.
  1. request 가 cancel 됐는지를 살피고 cancel 됐으면 finish 해준다.
  2. response 가 success 라면 response의 deliverResponse 그렇지 않다면 Request.deliverError
  3. 를 호출한다. 이 deliverResponse / deliveryError 부분은 이 volley library 를 사용할 때 user 가 직접 작성하는 부분이 된다.
  4. mResponse.intermediate 은 CacheDispatcher 부분에서 확인할 수 있는데, 별 뜻은 없고, Runnable 이 있으니, 그녀석을 처리하고 나서 request 를 finish 해야 한다는 뜻으로 지정해 놓은 녀석이다.




public class ExecutorDelivery implements ResponseDelivery {
    /** Used for posting responses, typically to the main thread. */
    private final Executor mResponsePoster;

    /**
     * Creates a new response delivery interface.
     * @param handler {@link Handler} to post responses on
     */
    public ExecutorDelivery(final Handler handler) {
        // Make an Executor that just wraps the handler.
        mResponsePoster = new Executor() {
            @Override
            public void execute(Runnable command) {
                handler.post(command);
            }
        };
    }

    ...

    @Override
    public void postResponse(Request<?> request, Response<?> response, Runnable runnable) {
        request.markDelivered();
        request.addMarker("post-response");
        mResponsePoster.execute(new ResponseDeliveryRunnable(request, response, runnable));
    }
    ...
    /**
     * A Runnable used for delivering network responses to a listener on the
     * main thread.
     */
    @SuppressWarnings("rawtypes")
    private class ResponseDeliveryRunnable implements Runnable {
        private final Request mRequest;
        private final Response mResponse;
        private final Runnable mRunnable;

        public ResponseDeliveryRunnable(Request request, Response response, Runnable runnable) {
            mRequest = request;
            mResponse = response;
            mRunnable = runnable;
        }

        @SuppressWarnings("unchecked")
        @Override
        public void run() {
            // If this request has canceled, finish it and don't deliver.
            if (mRequest.isCanceled()) {
                mRequest.finish("canceled-at-delivery");
                return;
            }

            // Deliver a normal response or error, depending.
            if (mResponse.isSuccess()) {
                mRequest.deliverResponse(mResponse.result);
            } else {
                mRequest.deliverError(mResponse.error);
            }

            // If this is an intermediate response, add a marker, otherwise we're done
            // and the request can be finished.
            if (mResponse.intermediate) {
                mRequest.addMarker("intermediate-response");
            } else {
                mRequest.finish("done");
            }

            // If we have been provided a post-delivery runnable, run it.
            if (mRunnable != null) {
                mRunnable.run();
            }
       }
    }
}


Reference