<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Seulgi Kim on Medium]]></title>
        <description><![CDATA[Stories by Seulgi Kim on Medium]]></description>
        <link>https://medium.com/@seulgi.kim?source=rss-9a008f6557a7------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*btyeQi7AsT6UJKhdO3J46A.jpeg</url>
            <title>Stories by Seulgi Kim on Medium</title>
            <link>https://medium.com/@seulgi.kim?source=rss-9a008f6557a7------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 07:52:33 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@seulgi.kim/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Do not use garbage collection to catch memory leak]]></title>
            <link>https://medium.com/codechain/do-not-use-garbage-collection-to-catch-memory-leak-a4e996d48c0f?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/a4e996d48c0f</guid>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[memory-management]]></category>
            <category><![CDATA[garbage-collection]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Fri, 10 May 2019 09:25:32 GMT</pubDate>
            <atom:updated>2019-05-10T09:50:56.046Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*pHyW9iGKjpw40GrMXYQAuQ.jpeg" /><figcaption><a href="https://pixabay.com/photos/lego-duplo-garbage-2498533/">https://pixabay.com/photos/lego-duplo-garbage-2498533/</a></figcaption></figure><p><a href="https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)">Garbage collection</a> is a technique that automatically releases unnecessary memory. It’s very famous because many programming languages adopted garbage collection after <a href="https://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)">John McCarthy</a> implemented it in Lisp. However, there are a few people who misunderstand what garbage collection does. If you think garbage collection prevents a memory leak, unfortunately, you are one of them.</p><p>Garbage collection cannot prevent a memory leak. There is no way to avoid all memory leaks if you are using a Turing-complete language. To understand it, you should know what a memory leak is. <a href="https://en.wikipedia.org/wiki/Memory_leak">Wikipedia</a> describes a memory leak as the following:</p><blockquote><em>a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released.</em></blockquote><p>Briefly, a memory leak is a bug that doesn’t release needless memory. So first, you need to find the memory that will not be used in order to detect memory leaks. Unfortunately, it is impossible. I’ll explain the reason with the code below. When should x be freed?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fd2dc875f27bd3f29b4e522e337d707a/href">https://medium.com/media/fd2dc875f27bd3f29b4e522e337d707a/href</a></iframe><p>Generally, x should be released after use(x). However, what if some_function does not end? If some_function never returns due to an infinite loop, use(x) will never be called. In this case, x has no future access. Thus, keeping this memory while running some_function is a memory leak. If you want to make this function free of memory leaks, you need to determine when to release x before executing some_function. It&#39;s impossible because this is <a href="https://en.wikipedia.org/wiki/Halting_problem">halting problem</a>. There is no way to static analyze whether some_function runs forever or not.</p><p>It’s the reason why there is no way to find all existing memory leaks. Therefore, all automatic memory management schemes, including garbage collection, don’t guarantee to catch all memory leaks. They merely try to release memory which applications will not use. They release only memory that apparently cannot be accessed, rather than freeing all unnecessary memory. Formally speaking, all automatic memory management schemes use a <a href="https://en.wikipedia.org/wiki/Soundness">sound</a> algorithm in the question “ <em>Is it safe to free this memory?</em>”, even though the algorithm is not <a href="https://en.wikipedia.org/wiki/Completeness_(logic)">complete</a>.</p><p>Releasing only memory which is safe to free is the goal of using garbage collection. Your program doesn’t have a <a href="https://en.wikipedia.org/wiki/Dangling_pointer">dangling pointer</a> if you use it instead of managing memory manually. It means you are free from use-after-free bugs or double-free bugs. In conclusion, garbage collection is not for memory efficiency, but memory safety.</p><p>If you are not familiar with memory management, you can reduce the number of memory leaks by using garbage collection. However, you should not choose garbage-collected languages to catch memory leaks. Furthermore, you should not be assured that your program doesn’t have a memory leak because you used garbage-collected languages. As I mentioned before, there is no method to catch all memory leaks. You should diagnose the source code manually to find them. You should use automatic memory management schemes, including garbage collection, as a tool to enhance safety.</p><p>This article is a translation of the article written in Korean. Please see <a href="https://medium.com/codechain-kr/garbage-collection%EA%B3%BC-memory-leak-47513d450045">this link</a> to see the original post.</p><p><em>Originally published at </em><a href="https://blog.seulgi.dev/2019/04/do-not-use-garbage-collection-to-catch-memory-leak.html"><em>http://blog.seulgi.dev</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a4e996d48c0f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain/do-not-use-garbage-collection-to-catch-memory-leak-a4e996d48c0f">Do not use garbage collection to catch memory leak</a> was originally published in <a href="https://medium.com/codechain">CodeChain</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Garbage collection과 memory leak]]></title>
            <link>https://medium.com/codechain-kr/garbage-collection%EA%B3%BC-memory-leak-47513d450045?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/47513d450045</guid>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[memory-management]]></category>
            <category><![CDATA[garbage-collection]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Thu, 09 May 2019 15:01:55 GMT</pubDate>
            <atom:updated>2019-05-10T02:02:24.684Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*pHyW9iGKjpw40GrMXYQAuQ.jpeg" /><figcaption><a href="https://pixabay.com/photos/lego-duplo-garbage-2498533/">https://pixabay.com/photos/lego-duplo-garbage-2498533/</a></figcaption></figure><p><a href="https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)">Garbage collection</a>(a.k.a. GC)은 프로그램이 더 이상 접근할 수 없는 메모리를 자동으로 해제시켜 주는 기술을 의미한다. <a href="https://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)">John McCarthy</a>가 Lisp에 처음 구현한 이후 많은 언어가 사용하여 현대 프로그래머 중에 모르는 사람이 없다고 해도 좋을 정도로 널리 알려진 개념이다. 근데 이 GC에 대해서 사람들이 자주 착각하는 것이 있다. GC를 사용하는 이유가 <a href="https://en.wikipedia.org/wiki/Memory_leak">memory leak</a> 을 잡아주기 위해서라고 생각하는 것이다. 만약 이렇게 생각했다면 GC에 대해 큰 착각을 하는 것이다.</p><p>GC는 memory leak을 막지 못한다. 사실 <a href="https://en.wikipedia.org/wiki/Turing_completeness">튜링 완전</a>한 언어에서 memory leak을 막아주는 방법은 세상에 존재할 수 없다. 이것을 설명하기 위해서는 우선 memory leak이 무엇인지 알아야 한다. <a href="https://en.wikipedia.org/wiki/Memory_leak">Wikipedia</a> 는 memory leak을 다음과 같이 설명한다.</p><blockquote><em>a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released.</em></blockquote><p>쉽게 설명해 memory leak이란, 사용하지 않을 메모리를 해제하지 않는 현상이다. 결국 memory leak을 잡기 위해서는 사용하지 않는 메모리를 찾아내는 것이 먼저다. 그리고 사용하지 않는 메모리를 완벽하게 찾아내는 건 불가능하다. 자세한 설명은 아래 코드를 통해서 하도록 하겠다.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/fd2dc875f27bd3f29b4e522e337d707a/href">https://medium.com/media/fd2dc875f27bd3f29b4e522e337d707a/href</a></iframe><p>위 코드에서 x는 언제 해제해야 할까? 보통은 use(x)가 끝난 뒤 해제해야 한다고 생각할 것이다. 하지만 some_function이 종료되지 않는 함수라면 어떨까? some_function이 내부에서 무한 루프를 돌고 절대 종료되지 않는 함수라면 use(x)는 호출될 일이 없다. 따라서 x는 앞으로 접근할 일이 없는 메모리고, some_function이 실행되고 있는 동안 x를 해제하지 않고 있는 것은 memory leak이다. 따라서 이 함수가 memory leak이 없다고 하려면 some_function이 실행되기 전에 이 함수가 종료되는 함수인지 아닌지 분석해서 x의 메모리 해제 시점을 결정해야 한다. 어떤 함수를 실행하기 전에 종료되는지 알 수 있다는 것은 <a href="https://en.wikipedia.org/wiki/Halting_problem">정지 문제</a>를 풀 수 있다는 것이므로 모순이다. 따라서 실행 전에 some_function 이 종료되는지 알 방법은 없다. 즉, memory leak을 완벽히 잡는 방법은 존재할 수 없다.</p><p>그래서 GC를 비롯한 메모리 관리 기술들은 전부 앞으로 사용하지 않는 메모리를 전부 해제하는 것을 보장하지 않는다. 대신 앞으로 사용하지 않는 것이 확실한 메모리만 해제하는 방식으로 동작한다. 즉, memory leak을 모두 잡는 대신 해제해도 안전한 메모리만 해제하는 것이다. 이를 조금 더 formal 하게 표현하면, ‘이 메모리를 해제해도 안전한가?’라는 질문에 <a href="https://en.wikipedia.org/wiki/Completeness_(logic)">completeness</a>는 포기하지만, <a href="https://en.wikipedia.org/wiki/Soundness">soundness</a> 를 보장하는 알고리즘으로 해제할 메모리를 찾는다고 할 수 있다.</p><p>모든 memory leak을 잡지는 못하지만, 해제해도 안전한 메모리만을 해제하는 것. 이것이 GC의 역할이다. GC를 사용하면 사용해야 할 메모리를 해제하지 않는다. 즉, <a href="https://en.wikipedia.org/wiki/Dangling_pointer">dangling pointer</a> 가 생기지 않는다는 것이고, 이에 따라서 double free나 use-after-free 같은 문제가 생기지 않는다. 즉, GC는 메모리 사용의 효율성이 아닌, 소프트웨어의 안정성을 올리는 도구라는 것이다.</p><p>GC를 썼더니 결과적으로 memory leak이 줄었다는 일은 있을 수 있다. 하지만 memory leak을 잡기 위해 GC가 있는 언어를 선택한다거나, GC가 있는 언어를 쓴다고 memory leak이 없을 것이라 생각하면 안 된다. 아쉽게도 memory leak은 사람이 소스를 분석해서 잡는 수밖에 없다. GC를 비롯한 메모리 관리 시스템은 전부 memory leak을 잡기 위한 기술이 아니라 해제해도 안전한 메모리만 해제하기 위한 기술로써 사용해야 한다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2019/04/garbage-collection-and-memory-leak.html"><em>https://blog.seulgi.kim</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=47513d450045" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/garbage-collection%EA%B3%BC-memory-leak-47513d450045">Garbage collection과 memory leak</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[read-writers lock — Accessing shared resources]]></title>
            <link>https://medium.com/codechain/read-writers-lock-accessing-shared-resources-39c277096a0f?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/39c277096a0f</guid>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[kodebox]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[multithreading]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Mon, 18 Feb 2019 08:52:05 GMT</pubDate>
            <atom:updated>2019-05-03T00:57:50.307Z</atom:updated>
            <content:encoded><![CDATA[<h3>Read-writers lock — Accessing shared resources</h3><p>In multithreaded programming, when accessing a shared resource, a <a href="https://en.wikipedia.org/wiki/Lock_%28computer_science%29">mutex</a> is used to ensure that not more than one thread is allowed to change resources simultaneously. A mutex guarantees safety because it restricts the number of threads accessing a shared resource to one, but in some cases, it can be inefficient. For instance, what if several threads need to access a shared resource at the same time, but only some of them change values? In this case, a thread that only reads values can be allowed simultaneous access. However, if a thread is changing the value, no other thread should access the shared resource. Conversely, while another thread is accessing a shared resource, the thread that wants to change a value should not access it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xnORJc2dqj0f6lbzMUDEew.jpeg" /></figure><p>What is used in situations like this is known as a <a href="https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock">readers-writer lock</a>, also known as a shared-exclusive lock. A readers-writer lock allows multiple readers and a single writer. It is also called a multiple-readers/single-writer lock(MRSW lock). In other words, if it acquires a read lock on a readers-writer lock that already acquired a read lock, it can immediately acquire a lock on it and execute the following code. However, if it acquires a write lock, a lock cannot be acquired and it must wait until the read lock is released.</p><p>If that’s the case, what happens if thread A acquires a read lock and thread B acquires a write lock and thread C acquires a read lock? It’s possible for one to think that thread A has acquired the read lock, so the write lock on thread B cannot be acquired and must wait, but the read lock on thread C can be acquired, and thus, threads A and C will be executed. However, in this implementation, if read locks are acquired frequently, then the write lock may not be executed indefinitely. This phenomenon is called a write-starvation.</p><p>Thus, some may implement a readers-write lock in a way that it waits for a write lock to be acquired without waiting for a new read lock if a write lock is waiting, even if a read lock is already acquired and a read lock can be acquired. In this case, the efficiency is lowered because the read lock is unnecessarily waited for and not acquired. However, the lock that started waiting earlier gets acquired first, and thus, the fairness factor rises. A write-starvation can occur, but an implementation that can effectively acquire a read lock is called read-preferring. Conversely, a slightly less efficient implementation is called write-preferring. Which of these is better depends on the situation. A write-preferring lock is a good idea if you can get a write-lock starvation due to frequent read locks. However, if you are not worried about write-starvation, the read-preferring implementation is lighter, and you can once again acquire a read lock on the same thread for MRSW locks that already acquired a read lock.</p><p>Some implementations specify that they use one of these policies; however, some implementations do not specify which policy is used. If a policy is not explicitly specified, usually, it is to leave room for future optimizations. In that case, you should write code that is suitable for both read-preferring or write-preferring.</p><p>Original Korean post: <a href="https://medium.com/kodebox/read-writers-lock-%EA%B3%B5%EC%9C%A0-%EC%9E%90%EC%9B%90-%EC%A0%91%EA%B7%BC%ED%95%98%EA%B8%B0-821f4af4d0b3">read-writers lock — 공유 자원 접근하기</a></p><p>Translated by <a href="https://medium.com/u/9f88b5a6c010">Seung Woo Kim</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=39c277096a0f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain/read-writers-lock-accessing-shared-resources-39c277096a0f">read-writers lock — Accessing shared resources</a> was originally published in <a href="https://medium.com/codechain">CodeChain</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[read-writers lock — 공유 자원 접근하기]]></title>
            <link>https://medium.com/codechain-kr/read-writers-lock-%EA%B3%B5%EC%9C%A0-%EC%9E%90%EC%9B%90-%EC%A0%91%EA%B7%BC%ED%95%98%EA%B8%B0-821f4af4d0b3?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/821f4af4d0b3</guid>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[multithreading]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Wed, 13 Feb 2019 01:40:20 GMT</pubDate>
            <atom:updated>2019-02-13T01:43:23.856Z</atom:updated>
            <content:encoded><![CDATA[<h3>read-writers lock — 공유 자원 접근하기</h3><p>Multithreaded programming에서 공유 자원에 접근할 때는 동시에 두 개 이상의 스레드가 자원을 변경시키지 않기 위해서 <a href="https://en.wikipedia.org/wiki/Lock_(computer_science)">mutex</a>를 사용한다. Mutex를 사용하면 공유자원에 접근하는 스레드를 한 개로 제한하기 때문에 안전하지만, 어떤 경우는 비효율적이다. 예를 들어 여러 스레드가 공유 자원에 동시에 접근해야 하지만 그중 일부 스레드만 값을 변경하는 경우는 어떨까? 이런 경우 값을 읽기만 하는 스레드는 동시에 접근해도 상관없다. 하지만 어떤 스레드가 값을 변경하고 있으면, 다른 스레드는 공유 자원에 접근해서는 안 된다. 반대로 다른 스레드가 공유 자원에 접근하고 있는 중에는 값을 변경하는 스레드는 접근해서는 안 된다.</p><p>이때 사용하는 것이 shared-exclusive lock이라고도 하는 <a href="https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock">readers-writer lock</a>이다. Readers-writer lock은 여러 개의 reader와 한 개의 writer를 허용한다. 그래서 multiple-readers/single-writer lock(MRSW lock)이라고도 불린다. 즉, 이미 read lock이 잡혀있는 readers-writer lock에 read lock을 잡으면 바로 lock이 잡히고 다음 코드를 실행할 수 있지만, write lock을 잡으면, lock을 잡지 못하고 read lock이 풀릴 때까지 기다린다.</p><p>그렇다면 <em>A thread</em>가 read lock을 잡고, <em>B thread</em>가 write lock을 잡은 뒤 <em>C thread</em>가 read lock을 잡으면 어떻게 될까? 단순하게 생각해보면 <em>A thread</em>가 read lock을 잡고 있으니 <em>B thread</em>의 write lock은 잡히지 못하고 기다리고, <em>C thread</em>의 read lock은 잡힐 수 있기 때문에, <em>A thread</em>와 <em>C thread</em>의 코드가 실행될 것이다. 하지만 이런 구현의 경우 read lock이 빈번하게 잡히는 코드라면, write lock이 영원히 실행되지 못할 수도 있다. 이 현상을 write-starvation이라고 부른다.</p><p>그래서 readers-write lock의 구현 중에서는 이미 read lock이 잡혀서 read lock을 잡을 수 있는 상황에서도 write lock이 기다리고 있으면 새 read lock은 잡지 않고, write lock이 잡히는 것을 기다리는 구현도 있다. 이 경우 불필요하게 read lock을 못 잡고 기다리는 경우도 있기 때문에 효율성은 떨어진다. 하지만 먼저 기다리기 시작한 lock이 먼저 잡히기 때문에 공정성은 올라간다. Write-starvation이 발생할 수 있지만, read lock을 효율적으로 잡을 수 있는 구현을 read-preferring이라고 부른다. 반대로 공정하지만, 효율성이 약간 떨어지는 구현을 write-preferring이라고 부른다. 이 둘 중 어느 쪽이 좋은지는 상황에 따라 다르다. read lock을 빈번하게 잡았다 풀어 write-lock starvation이 발생할 수 있는 경우는 write-preferring lock이 좋다. 하지만 write-starvation이 발생할 걱정이 없는 경우는 read-preferring의 구현이 더 가볍고, 이미 read lock이 잡혀있는 MRSW lock에 대해서 같은 스레드에서 다시 한번 read lock을 잡을 수 있다.</p><p>어떤 구현은 이 둘 중 한 가지 정책을 사용한다고 명시하지만, 구현에 따라서는 어떤 정책을 사용하는지 명시하지 않는 경우도 있다. 어떤 정책인지 명시하지 않은 경우는 대부분 추후에 최적화할 여지를 남겨두기 위해서이기 때문에 이 경우 read-preferring이든 write-preferring이든 안전하도록 코드를 짜야 한다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/12/rwlock.html"><em>blog.seulgi.kim</em></a><em> on February 13, 2019.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=821f4af4d0b3" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/read-writers-lock-%EA%B3%B5%EC%9C%A0-%EC%9E%90%EC%9B%90-%EC%A0%91%EA%B7%BC%ED%95%98%EA%B8%B0-821f4af4d0b3">read-writers lock — 공유 자원 접근하기</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Rust] _는 bind하지 않는다]]></title>
            <link>https://medium.com/codechain-kr/rust-%EB%8A%94-ownership%EC%9D%84-%EA%B0%96%EC%A7%80-%EC%95%8A%EB%8A%94%EB%8B%A4-5d679a1751d5?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/5d679a1751d5</guid>
            <category><![CDATA[lifetime]]></category>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[variables]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Thu, 09 Aug 2018 10:29:11 GMT</pubDate>
            <atom:updated>2018-10-23T07:07:51.306Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*Z9y56wAsa9e-nw7qzFgjcA.png" /></figure><p><a href="https://www.rust-lang.org/">Rust</a>는 <a href="https://en.wikipedia.org/wiki/Resource_acquisition_is_initialization">RAII idiom</a>을 사용하는 언어로, 객체가 소멸하는 시점에 따라 코드의 의미가 달라진다. 예를 들어 아래 코드를 보자.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c1bbd5dd1c346009b95c8a50dc973488/href">https://medium.com/media/c1bbd5dd1c346009b95c8a50dc973488/href</a></iframe><p>이 코드는 Service의 객체를 생성하고 종료하기를 기다리는 코드다. 이 코드는 문법적으로는 아무 문제가 없다. 하지만 종료할 때까지 Service가 어떤 동작을 수행하기를 원했다면 이는 틀린 코드다. Service 객체는 아무 변수에도 bind 되지 않았기 때문에 이 객체는 두 번째 줄에 있는 문장이 끝나면 소멸한다.</p><p>Service 객체가 wait_for_exit이 수행될 때까지 살아있기를 원한다면, 아래와 같이 변경해야 한다.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1a91471067dd95654ad4d976b9db1fe0/href">https://medium.com/media/1a91471067dd95654ad4d976b9db1fe0/href</a></iframe><p>위의 코드에서 Service의 객체는 변수 service에 bind 된다. 따라서 두 번째 라인이 끝나도 소멸하지 않고 wait_for_exit이 종료되는 것을 기다리고, run 함수가 종료되면서 stack이 unwind 될 때 소멸한다.</p><p>하지만 위의 코드를 컴파일하면 server가 unused variable이라는 경고가 보일 것이다. Rust 컴파일러는 선언된 변수가 사용되지 않으면 경고를 내기 때문이다. 그렇다면 사용하지 않는 변수의 소유권만 가지고 있고 싶을 때는 어떻게 해야 할까? 이 경우 _(underscore)로 시작하는 변수 이름을 사용하면 된다. Rust 컴파일러는 _로 시작하는 변수를 특별 취급하기 때문에, _로 시작하는 변수는 사용하지 않아도 컴파일러 경고가 나지 않는다.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/7b0774336a17d3e93d0adfb4dbc13d5c/href">https://medium.com/media/7b0774336a17d3e93d0adfb4dbc13d5c/href</a></iframe><p>그렇다면 사용하지 않는 변수에 아무런 이름을 주지 않으면 어떻게 될까? 어차피 사용하는 것이 목적이 아니고, 객체를 bind만 해서 가지고 있는 것이 목적이라면 아래 코드처럼 아무 이름 없이 _를 변수로 사용해도 되지 않을까?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/71ac2a830f2694637e6d046c071ab082/href">https://medium.com/media/71ac2a830f2694637e6d046c071ab082/href</a></iframe><p>아쉽게도 위 코드는 예상대로 동작하지 않는다. 이는 _가 객체의 소유권을 가지지 않기 때문이다. 이를 Rust의 용어로는 _는 value를 bind 하지 않는다고 말한다. 즉, 위의 코드는 Service 객체를 생성하고 소멸시킨 뒤 wait_for_exit 함수를 실행하는 <strong>service_run1.rs</strong>와 같은 코드다.</p><p>사실 이는 처음부터 의도된 동작은 아니었다. 2013년에 _에 넣은 값이 바로 drop 된다는 것이 <a href="https://github.com/rust-lang/rust/issues/10488">버그</a>로 보고됐고, _를 일반적인 변수와 같이 bind 하도록 고치자는 제안도 있었다. 사실, bind 하는 것이 더 직관적이고 일반적인 접근 방법이다. 하지만, Rust 개발자들은 _의 의미를 bind 하지 않는 것으로 스펙에 규정했다. 이는 어떤 값을 받아서 bind 하지 않는 방법이 기존에 존재하지 않았기 때문이다.</p><p>값을 bind 하지 않는 _의 특성은 다음과 같은 경우에 유용하게 사용된다.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6d86e7eb902d5959ec39378e20054810/href">https://medium.com/media/6d86e7eb902d5959ec39378e20054810/href</a></iframe><p>위 코드는 어떤 tuple을 받아서 Option&lt;A&gt;를 먼저 사용하고, 그 뒤 B를 사용한다. 만약 _가 값을 bind 하였다면, 네 번째 줄과 다섯 번째 줄에서 B가 move 되었을 것이다. 따라서 여덟 번째 줄은 이미 move 된 값을 사용하였다는 경고와 함께 컴파일되지 않았을 것이다. 하지만 _는 값을 bind 하지 않기 때문에 위의 코드는 성공적으로 컴파일된다.</p><p>여기서 _로 받은 값을 statement가 끝난 뒤 drop 하는 것이 아닌 값을 bind 하지 않는 것으로 정의했다는 것이 중요하다. 위의 <strong>service_run4.rs</strong> 예제에서 Service 객체가 drop 된 것은 temporary value를 bind 하지 않았기 때문이지 _가 값을 drop 시키기 때문이 아니다. 만약 _가 값을 drop 한다면, <strong>non_bind.rs</strong> 예제에서 match 문이 끝난 뒤 B가 drop 되기 때문에 여덟 번째 줄에서 B를 사용할 수 없었을 것이다.</p><p>개인적으로 이것 때문에 발생한 버그가 Rust를 사용하면서 겪었던 버그 중 해결에 가장 오랜 시간이 걸린 버그였다. 현재 개발 중인 <a href="https://github.com/CodeChain-io/codechain">CodeChain</a>은 멀티스레드 프로그램이기 때문에 <a href="https://github.com/CodeChain-io/codechain/blob/master/codechain/main.rs#L286">main thread에서 여러 개의 서비스를 생성하고 각 서비스는 종료될 때까지 자신이 해야 할 일을 한다.</a> 이때 대부분 서비스는 자기 완결적인 일을 하므로 외부에서 사용하지 않고 객체를 유지하기만 하면 된다. 따라서 변수의 이름을 _로 사용해도, 컴파일러 입장에서는 틀린 코드가 아니기 때문에 성공적으로 컴파일된다. 게다가 다른 언어에서는 _를 변수로 사용하는 것이 아무 문제 없기 때문에 코드를 읽어도 의심 없이 넘어갔었다.</p><p>이런 부류의 버그는 모르고 보면 잡기 어려운 문제지만, 알면 매우 쉬운 문제다. 하지만 Rust 공식 문서인 “The Rust Programming Language”에서도 “<a href="https://doc.rust-lang.org/stable/book/2018-edition/ch18-03-pattern-syntax.html#ignoring-an-unused-variable-by-starting-its-name-with-_"><em>However, using the underscore by itself doesn’t ever bind to the value. Listing 18–22 will compile without any errors because s doesn’t get moved into _.</em></a>”라고 단 두 줄 나오고 넘어가기 때문에 Rust의 _는 값을 bind 하지 않는다는 것을 모르기 쉽다. 그래서 앞으로 Rust를 쓰는 사람이 같은 버그를 만나지 않았으면 하는 마음으로 이 글을 쓴다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/08/rust--ownership.html"><em>blog.seulgi.kim</em></a><em> on August 9, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5d679a1751d5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/rust-%EB%8A%94-ownership%EC%9D%84-%EA%B0%96%EC%A7%80-%EC%95%8A%EB%8A%94%EB%8B%A4-5d679a1751d5">[Rust] _는 bind하지 않는다</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Skewed Merkle Tree]]></title>
            <link>https://medium.com/codechain-kr/skewed-merkle-tree-3df9964c4e7c?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/3df9964c4e7c</guid>
            <category><![CDATA[chaincode]]></category>
            <category><![CDATA[merkle-tree]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[skewed-merkle-tree]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Fri, 15 Jun 2018 07:56:35 GMT</pubDate>
            <atom:updated>2018-07-30T10:03:52.674Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://blog.seulgi.kim/2018/05/ethereum-secure-tree.html">지난번 글</a>에서 설명했듯이 <a href="https://www.ethereum.org/">이더리움</a>은 <a href="https://github.com/ethereum/wiki/wiki/Patricia-Tree">Modified Merkle Patricia Trie</a>를 4가지 용도로 사용한다. 이 중 State Trie와 Storage Trie는 변경되는 데이터를 효율적으로 저장하고 검증하기 위해서 사용된다. 하지만 Transaction Trie와 Receipts Trie는 변경되는 데이터가 대상이 아니다. 이 두 trie는 하나의 블록에서 사용된 트랜잭션과 그에 의해 생성된 receipt의 검증을 위해서만 사용되는 휘발성 데이터다.</p><p>이더리움이 두 가지 목적을 위해 같은 데이터 구조를 사용하는 이유는 같은 구현을 공유하기 위해서였다. 하지만 목적이 다르기 때문에 Transaction Trie나 Receipts Trie를 생성하는데 최적화된 코드는 State Trie나 Storage Trie를 생성하는데 필요한 코드와 다르다. 실제로 <a href="https://github.com/paritytech/parity/">Parity</a>는 각각의 용도로 다른 코드를 사용한다. 그렇다면 Transaction Trie나 Receipts Trie를 위해 애초에 같은 Trie를 사용할 이유가 없지 않았을까?</p><p>현재 코드박스에서 개발하고 있는 코드체인의 transactions_root와 invoices_root는 이런 고민이 반영됐다. 그래서 <a href="https://medium.com/codechain/codechains-merkleized-utxo-set-c76c9376fd4f">UTXO를 저장하는 Merkle Patricia Trie</a>와는 다른 구현을 사용하기로 결정했다. 그렇다면 transactions_root와 invoices_root에 필요한 특성은 무엇이 있을까?</p><p>최소한의 필요조건은 데이터를 검증할 수 있어야 한다는 것이다. 이 검증은 단순히 데이터셋을 검증할 뿐 아니라 데이터의 순서도 일치하는지 확인해야 한다. 여기까지가 이더리움을 비롯한 일반적인 블록체인에서 필요한 특성이다. 코드체인에서는 여기에 몇 가지 요구사항이 더 들어갔다.</p><p>우선 구현이 간단해야 한다. 간단해야 한다는 것은 코드가 단순하다는 것뿐 아니라 메모리 사용량이 적고, 실행하는데 시간이 적게 걸려야 한다는 것을 의미한다. 이는 코드체인이 라이트 클라이언트를 고려하고 있기 때문이다.</p><p>다음으로 전체 트랜잭션을 검증할 수 있어야 한다는 것이다. 이는 다른 블록체인에 없는 코드체인에만 존재하는 특성이다. 코드체인이 동기화를 맞추는 방법에는 Snapshot Sync가 있다. Snapshot Sync는 이력을 다 받을 필요 없이 신뢰할 수 있는 헤더 하나만 있으면 해당 블록을 받은 것과 같은 상태로 동기화되도록 하는 방법이다. 이를 위해서 하나의 헤더만으로 전체 트랜잭션을 검증할 수 있어야 한다.</p><p>마지막으로 incremental 하게 만들 수 있어야 한다. 코드체인의 transactions_root는 전체 트랜잭션 목록을 검증할 수 있어야 하기 때문에 incremental 하게 만들 수 없다면 블록이 쌓여갈수록 검증에 필요한 시간이 길어지게 된다. 이를 방지하기 위해 incremental 하게 만들 수 있어야 한다는 것이 필수적이다.</p><p>이런 조건들을 만족시키기 위해서 이더리움이 사용하는 Merkle Patricia Trie는 가장 먼저 배제됐다. 이는 전체 데이터에 대해서 incremental하게 만들 수 있지만 Trie를 구성하는데 드는 오버헤드가 컸다.</p><p>그다음으로는 전통적인 <a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle Tree</a>를 고려했다. 하지만 이는 위의 특성 중 오버헤드가 적어야 한다는 것과 incremental 하게 만들 수 있어야 한다는 것을 만족시키지 못했다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*y_zlfvtiDRgokT7hqJm70w.png" /></figure><p>그래서 우리는 왼쪽으로 치우친 Skewed Merkle Tree를 사용하기로 결정했다. Skewed Merkle Tree에서는 전 블록의 root위에 현재 블록의 트랜잭션들을 이용해 새 tree를 만들어 지금까지 실행된 전체 트랜잭션 목록을 담는 해시를 빠르고 가볍게 생성할 수 있다. 즉, 전체 트랜잭션 목록을 incremental 하게 만들 수 있고, 만드는데 드는 시간과 메모리는 트랜잭션 수에 선형적으로만 비례한다. 게다가 우리가 관심있는 것은 검증을 위한 root값 뿐이기 때문에 사용하는 메모리는 트랜잭션 개수와 상관없이 상수배만큼 사용하도록 최적화할 수 있다. 실제로 코드체인에서 사용한 코드는 다음과 같이 간단하다.</p><p>물론 Skewed Merkle Tree도 만능은 아니다. Skewed Merkle Tree는 Merkle Tree의 기본적인 기능인 Merkle path를 만드는 데 비효율적이다. 따라서 Merkle path를 만들어야 하는 경우 Skewed Merkle Tree보다 고전적인 balanced Merkle Tree가 더 적절하다. 하지만 코드체인이 transactions_root와 invoices_root를 사용하는 용도를 고려해봤을 때, Merkle-proof path를 사용하지 않는다. 오로지 데이터의 검증을 위해서만 사용하기 때문에 Skewed Merkle Tree가 더 적절하다고 판단했다.</p><p><strong>CodeChain 소스코드는 </strong><a href="https://github.com/CodeChain-io/codechain/wiki"><strong>github repo</strong></a><strong>에서 확인 가능합니다. 개발자간 실시간 소통을 위해 </strong><a href="https://gitter.im/CodeChain-io/codechain"><strong>gitter channel</strong></a><strong>도 운영중이니 들어오셔서 자세한 문의도 하시면 됩니다.</strong></p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/06/skewed-merkle-tree.html"><em>blog.seulgi.kim</em></a><em> on June 15, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3df9964c4e7c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/skewed-merkle-tree-3df9964c4e7c">Skewed Merkle Tree</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Modified Merkle Patricia Trie — ethereum이 상태를 저장하는 방법]]></title>
            <link>https://medium.com/codechain-kr/modified-merkle-patricia-trie-ethereum%EC%9D%B4-%EC%83%81%ED%83%9C%EB%A5%BC-%EC%A0%80%EC%9E%A5%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95-e385f7d6bf84?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/e385f7d6bf84</guid>
            <category><![CDATA[merkle-tree]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[ethereum]]></category>
            <category><![CDATA[planets]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Fri, 01 Jun 2018 08:55:34 GMT</pubDate>
            <atom:updated>2018-08-07T15:27:40.959Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://www.ethereum.org/">Ethereum</a>에서 네트워크 부분을 빼고 보면, Ethereum은 하나의 <a href="https://en.wikipedia.org/wiki/Finite-state_machine">state machine</a>이고, transaction은 ethereum의 state를 변경시키는 것이다. 이 state는 key-value pair로 표현된다. Key-value pair를 저장하는 방법은 여러 가지 있지만, ethereum에서는 state를 저장하기 위해 <a href="https://github.com/ethereum/wiki/wiki/Patricia-Tree">Modified Merkle Patricia Trie</a>(a.k.a. MPT)라는 특수화된 방법을 사용하도록 스펙에서 정의하고 있다.</p><p>MPT는 기본적으로 Patricia trie와 Merkle tree를 합친 것이다. 여기에 추가로 ethereum의 특성에 맞게 몇 가지 최적화를 했다. 따라서 MPT를 쉽게 이해하기 위해서는 Patricia trie와 Merkle tree를 아는 것이 좋다.</p><h4>Patricia Trie</h4><p>Patricia trie는 Prefix tree, radix tree, <a href="https://en.wikipedia.org/wiki/Trie">trie</a> 등 다양한 이름으로 불리는 자료구조다. Trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 있으며, 구현도 간단하다. 그래서 router 등 낮은 사양의 기계에 들어가는 routing table의 구현체로 많이 사용된다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*bOs4a86bBSAT83EX.png" /><figcaption><a href="https://commons.wikimedia.org/wiki/File:Trie_example.svg">https://commons.wikimedia.org/wiki/File:Trie_example.svg</a></figcaption></figure><h4>Merkle Tree</h4><p><a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle tree</a>는 hash들의 tree다. Leaf 노드에는 데이터를 보관한다. Leaf의 부모는 leaf의 hash를 가지고, 그 부모는 자식들의 hash의 합을 다시 hash 한 값을 가진다. Merkle tree는 leaf 노드를 제외한 노드들은 전부 hash를 가지고 있기 때문에 hash tree라고도 불린다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/0*jsJP-kKFk3xbJUp5.png" /><figcaption><a href="https://commons.wikimedia.org/wiki/File:Hash_Tree.svg">https://commons.wikimedia.org/wiki/File:Hash_Tree.svg</a></figcaption></figure><p>Merkle tree를 사용하면 서로 다른 두 노드가 같은 데이터를 가졌는지 효율적으로 비교할 수 있다. 예를 들어 위와 같은 <strong>L1</strong>, <strong>L2</strong>, <strong>L3</strong>, <strong>L4</strong>가 있을 때, 같은 Top Hash를 가졌는지만 비교하면 된다. 만약 Top Hash가 다르고, 어떤 데이터가 다른지 알고 싶으면 <strong>Hash0</strong>과 <strong>Hash1</strong>을 비교하고, 둘 중 다른 브랜치의 hash를 비교해나가면 어떤 데이터가 다른지 알 수 있다.</p><h4>Merkle Patricia Trie</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/0*RX3fjs3QVl_yaWqx.png" /></figure><p>MPT는 Merkle tree처럼 각 노드가 hash를 가진다. 노드의 hash는 노드 내용의 sha3 hash로 결정된다. 이 hash는 노드를 지칭하는 key로도 사용된다. <a href="https://github.com/ethereum/go-ethereum">go-ethereum</a>은 <a href="https://github.com/google/leveldb">leveldb</a>를, <a href="https://github.com/paritytech/parity">parity</a>는 <a href="https://rocksdb.org/">rocksdb</a>라는 <a href="https://en.wikipedia.org/wiki/Key-value_database">key-value storage</a>에 state를 저장한다. 이때 스토리지에 저장되는 key와 value는 ethereum state의 key-value가 아니다. 스토리지에 저장되는 value는 MPT 노드의 내용이고, key는 이 노드의 hash다.</p><p>대신 ethereum state의 key는 MPT에서 path로 사용된다. MPT에서 key가 같은지 비교하는 단위는 <a href="https://en.wikipedia.org/wiki/Nibble">nibble</a>이기 때문에 하나의 노드에서 최대 16개의 branch를 가질 수 있다. 거기에 노드도 값을 가지기 때문에, 16개의 브랜치와 값을 합쳐 17개의 아이템을 가진 배열이 <em>branch node</em>가 된다.</p><p>아래로 자식이 없는 노드는 <em>leaf node</em>라고 불린다. <em>Leaf node</em>는 자신의 path와 value 두 개의 아이템으로 이루어진 배열이다. 예를 들어 “0xBEA”라는 키에 1000이 들어있고, “0xBEE”라는 키에 2000이 들어있는 경우를 생각해보자. 그렇다면 “0xBE”를 path로 가지는 <em>branch node</em>가 있고, 그 아래 “0xA”와 “0xE”를 path로 가지는 두 <em>leaf node</em>가 붙는다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*Hnm-HmNYUN59Z2oH.png" /></figure><p>MPT에는 앞서 설명한 <em>branch node</em>와 <em>leaf node</em> 외에 <em>extension node</em>가 있다. <em>Extension node</em>는 <em>branch node</em>의 최적화다. Ethereum의 state에서는 하나의 <em>branch node</em>가 하나의 자식만 가지는 경우가 많다. 그래서 MPT는 하나의 자식만 가지는 <em>branch node</em>를 경로와 자식의 hash를 가지는 <em>extension node</em>로 압축한다.</p><p>여기서 문제가 하나 생긴다. <em>Leaf node</em>와 <em>extension node</em>는 둘 다 2개의 아이템을 가진 배열이다. 따라서 이 두 개의 node를 구분할 방법이 필요하다. MPT는 이를 위해서 경로에 prefix를 붙인다. 만약 노드가 <em>leaf node</em>고 경로가 짝수개의 nibble로 구성돼 있으면 0x20을 붙이고, 홀수개의 nibble로 구성돼 있으면 0x3을 붙인다. 반대로 <em>extension node</em>의 경우 짝수개의 nibble로 구성돼 있으면 0x00을, 홀수개의 nibble로 구성돼 있으면 0x1을 prefix로 붙인다. 홀수개의 nibble로 구성된 경로에는 한 개의 nibble을 prefix로 붙이고, 짝수개의 nibble로 구성된 경로에는 두 개의 nibble을 prefix로 붙이기 때문에 경로는 항상 byte로 표현 된다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/05/modified-merkle-patricia-trie.html"><em>blog.seulgi.kim</em></a><em> on June 1, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e385f7d6bf84" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/modified-merkle-patricia-trie-ethereum%EC%9D%B4-%EC%83%81%ED%83%9C%EB%A5%BC-%EC%A0%80%EC%9E%A5%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95-e385f7d6bf84">Modified Merkle Patricia Trie — ethereum이 상태를 저장하는 방법</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Secure Trie — state trie의 키가 256 bit인 이유]]></title>
            <link>https://medium.com/codechain-kr/secure-tree-state-trie%EC%9D%98-%ED%82%A4%EA%B0%80-256-bit%EC%9D%B8-%EC%9D%B4%EC%9C%A0-56398729746?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/56398729746</guid>
            <category><![CDATA[merkle-patricia-trie]]></category>
            <category><![CDATA[secure-tree]]></category>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[ethereum]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Fri, 01 Jun 2018 08:53:19 GMT</pubDate>
            <atom:updated>2018-08-07T15:27:24.166Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://blog.seulgi.kim/2018/05/modified-merkle-patricia-trie.html">지난번 글</a>에서 설명했듯이 ethereum의 상태는 modified Merkle Patricia Trie(a.k.a. MPT)에 저장된다. Ethererum에서 값은 nonce, balance 등 account의 상태고, 그 키는 account의 주소다. 이 Account의 주소는 160bit이기 때문에, MPT의 root에서부터 40 <a href="https://en.wikipedia.org/wiki/Nibble">nibble</a>의 경로를 타고 가면 account의 상태가 나와야 한다. 하지만 실제로 ethereum의 상태가 저장된 MPT에서 account의 주소를 키로 가지는 노드를 찾으면, <em>leaf node</em>가 아닌 <em>branch node</em>나 <em>extension node</em>가 나온다.</p><p>이는 ethereum이 account를 MPT에 집어넣을 때, account의 주소를 바로 키로 사용하는 것이 아니라, 주소의 keccak-256 hash를 키로 사용하기 때문이다. 즉, 40 nibble의 account 주소를 따라가는 것이 아니라, 64 nibble의 hash를 따라가야 원하는 account를 찾을 수 있다. 이렇게 account의 주소를 바로 경로로 사용하는 것이 아니라, 주소의 hash를 경로로 사용하는 것을 ethereum은 <strong><em>secure trie</em></strong>라고 부른다.</p><p><strong><em>Secure trie</em></strong>에 대해 자세히 설명하기 전에 ethereum이 사용하는 MPT에 대해서 더 알아야할 것이 있다. Ethereum에 있는 MPT는 state trie만이 아니다. Ethereum은 총 네 종류의 MPT가 있다.</p><p>첫 번째는 state trie다. 여기에는 ethereum의 account 정보가 저장된다. 여기서 account 정보는 account의 nonce, balance, storage root의 hash, code의 hash다. 만약 계정이 smart contract라면 storage root에는 smart contract의 state를 가지는 MPT의 root가 저장되고, code에는 evm bytecode의 hash 값이 저장된다.</p><p>두 번째는 storage trie다. etheruem의 smart contract는 내부 상태를 가진다. 따라서 smart contract인 account는 자신의 상태를 간직하는 storage trie를 하나씩 만들어서 가지고 있다.</p><p>나머지 두 개는 transactions trie와 receipts trie다. 이들은 각각 블록이 가지고 있는 트랜잭션들과 각 트랜잭션을 실행한 실행 결과를 배열로 했을 때, 배열의 인덱스를 키로 하는 MPT다. Transactions trie와 receipts trie는 merkle proof를 위해 사용된다.</p><p>이 네 개의 MPT 중에서 state trie와 storage trie만 <strong><em>secure tree</em></strong>를 사용하고, transactions trie와 receipts trie에는 secure tree를 사용하지 않는다. 즉, state trie와 storage trie는 keccak-256 hash 값인 256 bit 값을 키로 사용하고, transactions trie와 receipts trie의 키는 임의의 길이의 값이다.</p><p>Ethereum이 <strong><em>secure tree</em></strong>를 사용하는 이유는 <a href="https://en.wikipedia.org/wiki/Denial-of-service_attack">DoS 공격</a>을 막기 위해서다. State trie와 storage trie는 파일에 저장된다. 즉, 이 두 trie에 새 노드가 추가되거나, 수정하거나, 노드를 읽는 것은 disk IO가 있어야 하고, 가능하면 <em>leaf node</em>에 도착할 때까지 최대한 적은 노드를 지나서 가는 것이 좋다. MPT는 이를 위해서 중복되는 1-child <em>branch node</em>를 <em>extension node</em>로 압축할 수 있도록 했다.</p><p>하지만 자식이 하나인 <em>branch node</em>만 <em>extension node</em>로 압축된다. 따라서 공격자가 악의적으로 2개의 자식이 생기는 branch node를 만들 수 있다면, 적은 비용으로 공격할 수 있다. 그래서 <strong><em>secure tree</em></strong>는 keccak-256 hash 값을 키로 사용하여 공격자가 자신이 원하는 위치에 노드를 생성할 수 없도록 하였다.</p><p>Transactions trie와 receipts trie는 <strong><em>secure tree</em></strong>를 사용하지 않는 이유는 키를 hash 하는 것으로 보호할 수 있는 것이 없다. Transactions trie와 receipts trie에서 키는 트랜잭션과 receipt의 index기 때문에 공격자가 원하는 키를 삽입하는 것이 불가능하기 때문이다.</p><p>또한, <strong><em>Secure tree</em></strong>는 키가 256 bit로 고정된다는 장점도 있다. 덕분에 트리의 깊이가 64 이하라는 것이 보장되기 때문에 state trie나 storage trie의 임의의 값을 변경하는데 드는 최대 비용을 계산할 수 있다. 특히 state trie나 storage trie는 트랜잭션에 의해서 읽히거나 수정되는데, 이때 읽히거나 수정되는 값이 어떤 노드에 있는지 상관없이 같은 일을 하는 트랜잭션은 같은 비용을 낸다. 그렇기 때문에 최대 비용이 보장되는 것은 <strong><em>secure tree</em></strong>의 큰 장점이다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/05/ethereum-secure-tree.html"><em>blog.seulgi.kim</em></a><em> on June 1, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=56398729746" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/secure-tree-state-trie%EC%9D%98-%ED%82%A4%EA%B0%80-256-bit%EC%9D%B8-%EC%9D%B4%EC%9C%A0-56398729746">Secure Trie — state trie의 키가 256 bit인 이유</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Safety & Liveness — FLP impossibility으로 보는 블록체인]]></title>
            <link>https://medium.com/codechain-kr/safety-liveness-flp-impossibility%EC%9C%BC%EB%A1%9C-%EB%B3%B4%EB%8A%94-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-d963c7df8f5a?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/d963c7df8f5a</guid>
            <category><![CDATA[livenes]]></category>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[safety]]></category>
            <category><![CDATA[blockchain]]></category>
            <category><![CDATA[flp]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Thu, 24 May 2018 13:14:24 GMT</pubDate>
            <atom:updated>2018-10-23T07:42:19.826Z</atom:updated>
            <content:encoded><![CDATA[<p>블록체인이 유행하면서 블록체인의 수만큼 다양한 <a href="https://en.wikipedia.org/wiki/Consensus_(computer_science)">합의 알고리즘</a>이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까?</p><h3>FLP impossibility</h3><p>우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 consensus의 safety라고 말한다.</p><p>또한, 합의가 언젠가는 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 liveness가 보장된다고 말한다.</p><p>쉽게 풀어 말하면 safety는 “문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다”라는 것이고, liveness는 “문제없는 노드들은 반드시 합의를 한다”라는 것이다. 문제는 byzantine failure가 아닌 <a href="https://dl.acm.org/citation.cfm?id=214121">fail-stop failure가 하나만 있어도 safety와 liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다</a>. 이를 FLP impossibility 혹은 FLP theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 safety와 liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다.</p><h3>Liveness over Safety</h3><p><a href="https://en.wikipedia.org/wiki/Bitcoin">비트코인</a>이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 nakamoto consensus라고도 불린다. Nakamoto consensus는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면 언제든지 현재 합의된 블록을 다른 블록으로 대체할 수 있다. 이런 방식을 블록체인에서는 finality가 보장되지 않는다고 말하고 FLP impossibility에서는 liveness를 위해서 safety를 포기했다고 말한다.</p><p>Liveness를 중시하는 nakamoto consensus에서 출발한 합의 알고리즘들은 한정적인 상황에서 safety를 보장할 방법을 추가하는 방식으로 발전해갔다. <a href="https://www.ethereum.org/">이더리움</a>에서 구현되고 있는 <a href="https://arxiv.org/abs/1710.09437">Casper the Friendly Finality Gadget</a>이 대표적이다. Casper는 기존의 PoW로 liveness를 보장하며 블록을 생성하지만 50 블록마다 투표하여 safety가 보장되는 지점을 만든다.</p><h3>Safety over Liveness</h3><p>이와 반대로 safety를 중시하는 합의 알고리즘도 있다. 전통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다. <a href="https://cosmos.network/">Cosmos</a>에서 사용하는 <a href="https://tendermint.com/">Tendermint</a>가 대표적인 safety를 보장하는 BFT 알고리즘이다.</p><p>Tendermint는 하나의 라운드가 propose, prevote, precommit 3개의 단계로 나누어진다. 이 중 prevote와 precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어진다. 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다. 하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못 하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있다. 따라서 liveness는 보장되지 않는다.</p><p>FLP impossibility가 증명했듯이 safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 liveness를 보장할 수 없다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 liveness가 보장됨을 증명한다.</p><p>비동기 네트워크 모델에서는 메시지가 전송되는 것이 보장되는 시간이 없다. 이는 메시지가 무한한 시간 후에 도착하는 것도 가정해야 하고 다시 말해서 전송한 메시지가 도착하지 않는 것을 가정해야 한다. 그렇다고 해서 정해진 시간 안에 메시지 전달이 보장되는 동기 네트워크 모델을 사용할 수는 없다. 이는 인터넷 규모의 네트워크에서는 비현실적인 가정이고, 이런 가정에서 liveness를 증명하는 것은 아무 의미 없기 때문이다. 그래서 tendermint는 정해진 시간 안에 메시지가 도달하는 것이 보장되지만 그 정해진 시간을 알 수 없다는 <a href="https://dl.acm.org/citation.cfm?id=42283">partial synchronous network model</a>을 사용한다.</p><p>Partial synchronous network는 정해진 시간 내에 메시지가 도착하는 것이 보장되는 모델이다. 다만 이 정해진 시간이 무엇인지 노드는 알지 못한다. 이는 꽤나 현실적인 모델이다. 현실의 네트워크도 omission failure가 발생하지 않는 한 언젠가는 메시지가 도착하기 때문이다.</p><p>BFT 계열의 합의 알고리즘은 블록 생성을 위해 2번의 투표를 모아야 한다. 비록 partial synchronous network model에서는 언젠가 합의될 것이 보장되지만, 최악의 경우 몇번의 라운드 동안 새 블록이 생성되지 않는 경우도 생긴다. 이는 TPS 저하를 초래한다.</p><p>BFT 계열 알고리즘은 이런 문제를 해결하기 위한 방향으로 발전해왔다. 2018년 3월에 발표된 <a href="https://arxiv.org/pdf/1803.05069.pdf">Hot-stuff</a>이라는 프로토콜이 대표적이다. Hot-stuff에서 블록은 validator들의 투표를 포함한다. 이 투표를 commit-certificate(a.k.a. CC)이라고 한다. Hot-stuff은 기존의 BFT 계열의 알고리즘과 다르게 CC가 없는 블록도 생성될 수 있다. 그저 이 블록들은 finality가 보장되지 않을 뿐이다. 이 CC가 없는 블록들은 뒤에 CC가 있는 블록의 finality가 보장되면 그때 finality가 보장된다. 시간 당 블록 생성량을 올리기 위해서 safety를 어느 정도 포기하는 것이다.</p><h3>마치며</h3><p>이상으로 liveness의 극단에 있는 nakamoto consensus에서부터 safety에 극단에 있는 tendermint까지 블록체인에서 사용되는 다양한 합의 알고리즘을 알아봤다. 중요한 것은 safety와 liveness는 trade-off이지 둘 중 누군가가 더 우월한 특성은 아니라는 것이다. 자신이 구현하려는 서비스의 종류에 따라 safety와 liveness가 어느 정도 필요한지를 판단하여 알맞은 합의 알고리즘을 사용하는 블록체인을 선택해야 한다.</p><p><em>Originally published at </em><a href="https://blog.seulgi.kim/2018/05/safety-liveness-in-blockchain.html"><em>blog.seulgi.kim</em></a><em> on May 24, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d963c7df8f5a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/safety-liveness-flp-impossibility%EC%9C%BC%EB%A1%9C-%EB%B3%B4%EB%8A%94-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-d963c7df8f5a">Safety &amp; Liveness — FLP impossibility으로 보는 블록체인</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Byzantine Failure — 블록체인 개발이 어려운 이유]]></title>
            <link>https://medium.com/codechain-kr/byzantine-failure-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%EA%B0%9C%EB%B0%9C%EC%9D%B4-%EC%96%B4%EB%A0%A4%EC%9A%B4-%EC%9D%B4%EC%9C%A0-16f3936092dd?source=rss-9a008f6557a7------2</link>
            <guid isPermaLink="false">https://medium.com/p/16f3936092dd</guid>
            <category><![CDATA[failure-model]]></category>
            <category><![CDATA[byzantine]]></category>
            <category><![CDATA[planets]]></category>
            <category><![CDATA[blockchain]]></category>
            <dc:creator><![CDATA[Seulgi Kim]]></dc:creator>
            <pubDate>Fri, 18 May 2018 09:22:08 GMT</pubDate>
            <atom:updated>2018-05-29T04:25:58.946Z</atom:updated>
            <content:encoded><![CDATA[<p>2017년에 이어 올해 2018년까지 블록체인은 정말 시대의 대세가 됐다. 결국, 개발자 외에도 많은 사람이 블록체인을 이야기하고 있다. 그 사람들에게 블록체인이 어려운 이유를 말하라고 하면 대부분 블록체인은 단순한 기술을 넘어서 화폐이기 때문에 어렵다고 말한다. 하지만 이건 사실이 아니다. 가장 유명한 블록체인 시스템인 <a href="https://en.wikipedia.org/wiki/Bitcoin">비트코인</a>이 대표적인 <a href="https://en.wikipedia.org/wiki/Cryptocurrency">암호화폐</a>이기 때문에 사람들이 흔하게 하는 착각이다. 하지만 기술적으로 블록체인이 화폐일 이유는 없다.</p><p>블록체인을 조금 더 공부한 사람에게 물어보면 블록체인은 incentive model을 설계해야 해서 어렵다고 말한다. 블록체인에서는 사용자들의 자발적 참여를 유도하기 위한 incentive model을 설계해야 하고, 이는 결국 사람 심리의 영역이기 때문에 어렵다는 것이다. 하지만 이것도 블록체인이 어려운 근본적인 이유는 아니다. 블록체인이 어려운 이유는 블록체인이 분산환경에서 풀어야 하는 가장 어려운 문제를 풀기 때문이다.</p><p>분산 시스템은 여러 개의 노드 사이에서 메시지를 주고받으며 상태를 변화시킨다. 이때 모든 노드가 정상적인 경우만 가정할 수는 없다. 이런 시스템은 단일 노드에서 처리되는 시스템보다 문제가 발생할 확률이 늘어나기 때문이다. 하지만 현실적으로 모든 에러를 처리할 수는 없다. 그래서 일반적으로 분산 시스템은 자신이 감당할 수 있는 에러를 정의하고, 그 이외의 에러가 발생할 경우는 동작을 보장하지 않도록 설계된다. 이때 감당할 수 있는 에러의 종류를 시스템의 Failure Model이라고 부른다.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/0*7PX5Uc_MUEhRSNSR.png" /></figure><p>전통적으로 분산 시스템에서 Failure Model은 6개로 분류된다. 이 6 분류는 계층을 가지고 있기 때문에 더 큰 부류는 작은 부류를 포함한다. 분산 시스템은 목표로 하는 Failure Model을 설정하고 그보다 큰 부류의 failure가 발생했을 때는 처리를 포기한다.</p><p>가장 처리하기 쉬운 문제는 Fail-stop Failure Model이다. Fail-stop Failure Model에서는 문제가 발생한 노드는 더 이상 상태가 변하지 않지만, 문제가 발생하기 전 상태를 돌려준다. Fail-stop Failure Model에서는 항상 요청한 메시지가 도착하고, 도착한 메시지는 정상이라고 가정하기 때문에 문제가 쉽게 풀린다. 하지만 메시지가 도착하지 않을 수 있는 현실적인 모델, 간단하게는 서버가 crash나는 상황에 대해서는 고려조차 돼있지 않기 때문에 많이 사용되지 않는다.</p><p>그래서 그 다음으로 사용되는 모델은 crash를 고려하는 Crash Failure Model이다. 이 모델에서 요청에 대해 응답을 주지 않는 노드는 언제나 crash 났다고 가정한다. 응답을 주지 않는 노드가 있을 때는 문제가 발생한 노드를 대체하는 새 노드를 실행시키는 것만으로 문제를 해결할 수 있다. 하지만 Crash Failure Model도 인터넷 스케일의 분산 시스템에서는 현실적이지 않다. 인터넷 스케일에서는 노드가 crash나는 것 이외에도 다양한 이유로 메시지가 도착하지 않을 수 있기 때문이다. 그래서 Crash Failure Model은 보통 <a href="https://en.wikipedia.org/wiki/Multi-core_processor">멀티코어 프로세서</a>에서 프로세서 간 통신이나, 한 <a href="https://en.wikipedia.org/wiki/Data_center">데이터 센터</a> 내에서 구성되는 분산 시스템에서 많이 사용된다.</p><p>인터넷 스케일에서 사용할 수 있는 가장 간단한 모델은 Omission Failure Model이다. Omission Failure Model은 일정 단위 시간 T를 정의하고 모든 메시지는 전송 후 T 시간 이내에 도착하거나 영원히 도착하지 않을 것이라고 가정한다. 이는 네트워크에서 발생하는 문제를 매우 간단하게 모델링한 것이다.</p><p>하지만 실제 네트워크에서는 이보다 복잡한 이슈가 발생한다. 메시지가 도착하는 maximum bound인 T를 정하는 것은 사실상 불가능하다. 현실적으로는 문제가 발생했을 때 메시지는 안 올 수도 있지만, 매우 늦게 도착할 수도 있다. 이런 상황을 고려한 모델을 Performance Failure Model이라고 한다. Performance Failure Model을 가정하는 분산 시스템은 메시지가 안 도착하거나 매우 늦게 도착하는 상황까지 고려해야 한다.</p><p>지금까지 설명한 문제는 전부 메시지가 도착했다면 제대로 된 메시지가 도착했다고 가정한다. 다시 말해서 지금까지 설명한 네 개의 failure model. 즉, Fail-stop Failure Model, Crash Failure Model, Omission Failure Model, Performance Failure Model에서는 일단 메시지가 도착하면 그 메시지를 믿는다. 하지만 현실적으로는 믿을 수 없는 경우가 있다. 어떤 노드에 버그가 발생하거나 하드웨어 문제로 메시지가 일부만 전송됐을 수도 있다. 최악의 경우에는 <a href="https://en.wikipedia.org/wiki/Man-in-the-middle_attack">Man-in-the-middle</a>(a.k.a. MITM) 공격 때문에 메시지가 변조될 수도 있다.</p><p>일관되게 잘못된 메시지만 보내는 노드만 있는 경우 어렵지 않게 해결된다. 하지만 어떤 메시지는 제대로 보내고 어떤 메시지는 검증 불가능한 잘못된 메시지를 보내는 경우라면 문제가 어려워진다. 이렇게 일관성 없게 잘못된 메시지를 보내는 노드를 byzantine node라고 부르고 이런 failure를 byzantine failure라고 부른다.</p><p>일반적으로 모든 byzantine failure를 처리하는 것은 어려운 일이다. 그래서 byzantine failure 중에서 검증할 수 있는 byzantine failure만을 처리겠다는 모델을 Authentication-detectable Byzantine Failure Model이라고 부른다. Authentication-detectable Byzantine Failure Model에서는 <a href="https://en.wikipedia.org/wiki/Error_detection_and_correction">error detection scheme</a>을 넣거나 <a href="https://en.wikipedia.org/wiki/Public-key_cryptography">비대칭 암호화</a>를 하는 방식으로 문제를 해결한다. 현재 사용되는 인터넷 규모의 분산 시스템은 대부분 Authentication-detectable Byzantine Failure Model을 가정한다.</p><p>하지만 블록체인은 모든 byzantine failure를 고려하는 Byzantine Failure Model을 가정한다. 이는 분산 시스템에서 가정할 수 있는 가장 풀기 어려운 모델이다. 그래서 기존에 있던 분산 시스템은 대부분 byzantine failure를 의도적으로 무시했다. 대부분 노드가 비정상적으로 동작하거나 악의적으로 동작하거나 해킹당하여 이상한 동작을 하는 경우를 고려하지 않았다.</p><p>블록체인의 복잡한 개념들은 전부 블록체인이 Byzantine Failure Model을 사용하기 때문이다. 예를 들어 사람들이 어려워하는 incentive model은 참여자들이 자발적으로 byzantine node가 되지 않도록 하기 위한 유인을 주는 것이고, <a href="https://en.wikipedia.org/wiki/Consensus_(computer_science)">합의 알고리즘</a>이 복잡해지는 것도 byzantine failure를 가정하기 때문이다. 그렇다면 Byzantine Failure Model을 사용하지 않으면 문제가 단순해지지 않을까?</p><p>아쉽게도 이는 불가능하다. 블록체인은 자발적으로 참여하는 탈중앙화된 노드로 구성된 네트워크이기 때문이다. 탈중앙화된 네트워크에서 byzantine node를 발생시키는 이유는 다양하다. 가장 흔한 경우는 악의적인 사용자들이 있다. 단순한 취미로 혹은 경제적인 이유로 혹은 개인적인 원한으로 시스템을 공격하는 사례는 많이 있다. 노드로 참여하는 것이 자유롭지 않은 기존 시스템에서는 보통 <a href="https://en.wikipedia.org/wiki/Denial-of-service_attack">DoS</a> 공격을 한다. 하지만 참여가 자유로운 블록체인에서는 byzantine node가 되어 일관성 없는 동작으로 공격하는 것이 더 효과적이다.</p><p>악의가 없더라도 게으른 사용자들도 byzantine node가 된다. 중앙화된 분산 시스템에서는 시스템 업그레이드가 빠르고 쉽다. 중앙 관리자가 시스템을 전부 업그레이드하면 끝나기 때문이다. 하지만 탈중앙화된 네트워크에서는 그렇지 않다. 일부 노드는 업그레이드해도 게으른 사용자들은 업그레이드하지 않을 수 있다. 이 경우 업그레이드하지 않은 노드들은 업그레이드된 노드의 메시지를 이해하지 못해 byzantine failure를 발생시킬 수 있다.</p><p>이상으로 블록체인이 어려운 이유, Byzantine Failure에 대해서 알아봤다. 블록체인에 관심 없는 엔지니어에게 블록체인에 관해 물어보면 블록체인은 “이력을 저장하는 <a href="https://en.wikipedia.org/wiki/Distributed_data_store">분산 저장소</a>”라고 대답한다. 하지만 이는 블록체인의 극히 단편적인 모습만을 본 것이다. 오히려 이력을 저장한다는 특징은 byzantine failure를 극복하려는 방법에 불과하다. 블록체인은 근원적으로 이보다 어려운 문제를 풀어야 한다.</p><p>개인적으로는 이 어려움이 블록체인 개발의 재미라고 생각한다. 기존에는 이론적으로 연구만 되던 것이 실제로 동작하는 구현체가 나오고 있다. 특히 byzantine failure는 failure model 중 가장 현실에 가까운 모델이다. 따라서 앞으로 나오는 분산 시스템은 Byzantine Failure Model을 가정하고 나올 것이다. 그래서 설령 블록체인 개발을 하지 않더라도 블록체인에서 어떤 연구가 되고 있는지 아는 것은 분산 시스템 개발자로서도 중요하다고 생각한다.</p><p><em>Originally published at </em><a href="http://blog.seulgi.kim/2018/05/byzantine-failure-why-blockchain-is-hard.html"><em>blog.seulgi.kim</em></a><em> on May 18, 2018.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=16f3936092dd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codechain-kr/byzantine-failure-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%EA%B0%9C%EB%B0%9C%EC%9D%B4-%EC%96%B4%EB%A0%A4%EC%9A%B4-%EC%9D%B4%EC%9C%A0-16f3936092dd">Byzantine Failure — 블록체인 개발이 어려운 이유</a> was originally published in <a href="https://medium.com/codechain-kr">코드체인</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>