마스트 편집하기

'''마스트'''(MAST; Merklized Abstract Syntax Trees)는 [[비트코인]]에 제안된 추가 기능으로, 더 작은 거래 규모, 더 많은 개인 정보 보호 및 더 큰 [[스마트 계약]]을 허용한다. 마스트의 기본 사항을 살펴보고 잠재적 이점을 설명하고 [[비트코인 프로토콜]](Bitcoin Protocol)에 추가하기 위한 현재 제안 중 일부를 요약한다.

==개요==
현대 [[암호]] 시스템의 맥락에서 공통 주제 분산 트러스트 네트워크를 만드는 것이다. 이들 대부분 설계, 계약의 영구 저장이 필요하다. 그러나 영구 스토리지는 주요 성능이 될 수 있다. 비용 병목 현상. 결과적으로 좋은 코드 압축체계는 이러한 계약 기반 암호화 시스템을 확장하는 데 중요한 요소이다. 이 프로젝트를 위해 우리는 공식화하고 "Merkelized Abstract Syntax Tree"라는 데이터 구조(MAST)는 데이터 [[무결성]]과 압축을 모두 해결한다. 마스트를 사용하면 원격으로 실행될 계약 [[프로그램]]을 간결하게 표현할 수 있다.<ref name="제레미 루빈">〈[http://reurl.kr/32844142LX 마스트]〉,《마스트 백서》 </ref>

==데이터 구조==
마스트는 [[머클트리]](Merkle Trees) 와 [[AST]](Abstract Syntax Trees)의 특성을 결합하여 프로그램을 간결하고 안전하게 표현한다. 머클트리는 데이터의 무결성을 효율적으로 검증하는 데 사용 저장, 데이터 블록은 리프 [[노드]]에 저장되며 비 리프 노드는 하위 노드의 레이블 [[해시]]이다. [[비트코인]] [[블록체인]]에서 머클트리는 현재 거래 내역을 효율적으로 저장하는 데 사용된다. AST, 반면에, 프로그램의 구문 구조를 나타낸다. 프리미티브는 AST의 리프 노드에 있으며 비 리프 노드는 프로그래밍 작업을 나타내고 제어 흐름 메커니즘 MAST에서 트리의 루트는 다른 모든 노드는 서브 프로그램을 나타낸다. 트리의 각 경로는 다른 실행 분기이다.<ref name="제레미 루빈"></ref>

*'''머클트리''' : 머클트리 구조는 [[랄프 머클]](Ralph Merkle)이라는 사람이 1979년에 만들어 낸 개념이다. 다른 트리 [[알고리즘]]과는 다르게 머클트리의 목적은 빠른 검색이 아니라 데이터의 간편하고 확실한 인증을 위해 사용한다. 머클트리의 최상위 부모노드 혹은 루트는 머클루트라 부르며 블록체인의 원소역할을 수행하는 [[블록]]에서 지정된 [[트랜잭션]]들의 해시트리라 볼 수 있다. 머클트리는 데이터의 간편하고 확실한 인증을 위해서 SHA-256 암호화 기술(해시함수)을 사용하고 있다.<ref>불곰, 〈[https://brownbears.tistory.com/372 머클트리(merkle tree)란?]〉, 《티스토리》, 2018-07-09</ref>{{자세히|머클트리}}

*'''AST''' : [[AST]]란 abstract syntax tree의 약어로 추상 구문 트리 또는 간단히 구문 트리라고 불린다. AST는 [[프로그래밍 언어]]로 작성된 소스 코드의 추상 구문 구조의 트리이다. 이 트리의 각 노드는 소스 코드에서 발생하는 구조체를 나타낸다. 구문이 추상적이라는 의미는 실제 구문에서 나타나는 모든 세세한 정보를 나타내지는 않는다는 것을 의미한다.

==거래 지출==
[[비트코인]]의 지출은 [[P2SH]]에서와 아주 비슷하지만, 마스트에서는 비트코인이 머클루트에 잠겨 있는데, 이는 개별적인 조건을 해치고 [[머클트리]]에 쌓음으로써 파생된 것이다. 그래서 Merklized address에서 이 비트코인 출력을 사용하려면 [[스크립트]], 스크립트 해시(머클루트), 그리고 동전의 잠금을 풀기 위한 서명과 같은 다른 요구사항들을 생산해야 한다. 하지만, 마스트에서는 전체 스크립트 집합을 포함할 필요가 없고 대신에 실제로 사용되고 있는 스크립트만 만들 수 있다. 비트코인 고객은 머클 증명 기술을 사용하여, 실제 사용 중인 스크립트의 해시를 실행하고 생산할 수 있으며, 이는 머클 루트에 대해 검증할 수 있다. 이제 사용 중인 조건의 해시와 머클 루트가 그 조건이 원래 조건 집합의 일부였는지를 확인하기에 충분하므로, 당신은 이제 작은 거래를 하게 되었다. 그리고 이것이 확인되면 [[블록체인]]은 동전이 이 스크립트에만 잠겨 있다는 것을 알게 되고 거래가 성사된다. 이 예상치 못한 스크립트 가지를 숨기는 구조는 각각의 조건이 머클트리의 잎인 복잡한 상황 조건을 가질 수 있게 해준다. 돈을 쓸 때, 다른 정보나 가지를 보여주지 않고 단지 그 가지에 머클트리의 일부였다는 증거를 더하면 된다. 이러한 것을 마스트가 가능하게 만들어 준다.<ref>Sudhir Khatwani,〈[https://themoneymongers.com/merkelized-abstract-syntax-tree-mast/ Bitcoin's Merkelized Abstract Syntax Tree(MAST) Explained!!]〉, 《TheMoneyMongers》, 2019-08-13</ref>

==장점==
*[[비트코인]] [[스마트 계약]]의 유연성을 향상시키고, 프라이버시를 증가시키며, 확장성을 크게 돕는다.
*비트코인을 잠글 때 마스트를 이용해 여러 가지 복잡한 형태의 조건을 표현할 수 있어서, 1000종 중 1종이나 200종 중 20종 같은 멀티시그 계약을 쉽게 할 수 있다.
*전체 집합 대신 사용하는 [[트랜잭션]]에 해당 조건만 포함하도록 요구하므로 데이터 이점이 있다. 이렇게 하면 복잡한 잠금 해제 조건과 동시에 거래 규모가 훨씬 작아진다. 이것은 또한 당신이 P2SH를 사용하는 동안 지불하는 거래 수수료를 줄인다.
*마스트를 사용하면 추가적인 프라이버시를 얻을 수 있다. 마스트 거래를 보면 관련된 조건이 있다는 것을 짐작할 수 있을 뿐, 그러한 조건들이 무엇인지 혹은 어떤 것인지 결코 알 수 없을 것이다. 그러나 누군가가 마스트를 이용해 프라이버시를 달성하려는 거래를 보면 알 수 있다는 사실은 사생활의 허점이며, 비트코인 개발자들은 비트코인 타프로트라고 알려진 또 다른 기법으로 이 문제를 고치려 하고 있다.

==구현==
===마스트노드===
*마스트노드는 문자열 내용과 부모 포인터로 구성된다. 
*문자열 내용은 실행할 수 있는 코드이며 [[마스터노드]]는 여러 개의 자식을 가질 수 있다. 
*각각은 서로 다른 프로그램 실행 분기를 나타내며 addBr 메소드를 통해 새 분기를 추가 할 수 있다. 
*경로를 따라서 각 [[노드]]의 모든 문자열 내용 결합 따라서 마스트 에서 하나의 가능한 경로에 대한 코드를 생성한다.

마스트의 가지들은 어떤 특정한 순서로 추가될 필요가 없기 때문에, 트리 건설 하는 동안 일관성을 유지하는 것은 번거로울 것이다. 대신, 마스트노드의 해시함수는 트리의 현재 상태를 이용하여 정확한 머클 해시를 계산한다. 그것은 먼저 모든 직계 자식 노드의 이진트리를 형성함으로써 그렇게 한다. 이 트리가 생성되면 해시는 결합하여 이진트리의 각 수준에서 새로운 머클 해시를 생성한다. 이진트리에 노드의 내용을 포함하지 않음으로써, 부모가 자식보다 먼저 실행하는 추상 구문트리 스타일 구조를 확립한다.<ref name="제레미 루빈"></ref>

===증명 목록===
코드의 무결성을 확인하기 위해 마스트 함수 "generateFullProofUpward"는 현재 노드에서 주어진 머클 루트 해시에 대한 증명 목록(Proof list)을 생성한다. 트리를 위쪽으로 통과시키고, 머클 해시 목록과 그것이 지나가는 코드 내용을 생성하는 것이다. 머클 해시는 이진트리를 사용하여 계산하기 때문에 논리는 더욱 복잡해진다. 결과적으로 증명 목록 생성기는 분기 머클 루트에 도달할 때까지 이 이진트리를 기어 올라 목적지 노드에 도달할 때까지 프로세스를 반복한다. 검증 프로세스의 경우, 다른 기계에 마스트 루트 노드의 머클 해시가 있다고 가정한다. 대상 노드가 마스트 루트 해시인 증명 목록을 사용하면, 이 다른 기계는 그것을 반복하여 증명 목록의 코드를 확인할 수 있고, 해시값을 합쳐서 증명 목록의 다음 해시값에 더하는지 확인할 수 있다. 최종 합계가 루트 해시를 산출한다면, 제공된 해시의 순서가 정확하다. 우리는 내용 해시가 표시됨에 따라 증명 목록의 해시에 대한 코드의 물결성을 점검한다. 또한 [[스크립트]]는 [[비트코인]] [[블록체인]]에서 사용되는 [[옵코드]](opcode)와 호환되는 증명 형식으로 컴파일할 수 있다. 어떠한 마스트도 블록체인 위에 올리지 않고, 우리가 쓴 비트코인 스크립트 해석기를 통해 테스트했다. 이는 우리의 마스트 구현과 비트코인 [[프로토콜]] 사이의 호환성을 더욱 강화시키고 이 프로젝트의 잠재적인 장래성을 비트코인 블록체인 내에 통합할 수 있게 해준다.

===컨센서스 프로토콜 시물레이션===
마스트를 사용하여 [[네트워크]]를 통해 전송되는 코드를 확인하고 실행하기 위해 암호화폐 네트워크 시뮬레이터를 구현했다. [[비트코인]]에 사용되는 [[트랜잭션]] 검증 프로세스를 시물레이션하기 위해 [[합의노드]] 개체를 생성하여 트랜잭션에서 코드를 실행하고 검증하였다. 합의노드는 GoodNode, EvilNode, InconsistenNode 세 가지 유형을 구현했다. GoodNode는 코드를 적절하게 실행하고, 유효한 경우 로컬 리더에 트랜잭션을 포함한다. EvilNode는 유효하지 않은 트랜잭션을 해당 리더에 추가하고 유효한 트랜잭션을 제외할 수 있다. InconsistenNode는 어느 정도의 확률로 올바르게 동작한다. 3개의 노드 유형을 사용하여, 더욱 현실적인 네트워크 조건과 적들의 존재를 시뮬레이션할 수 있다. 합의노드는 다른 유형의 적들을 시뮬레이션하기 위해 추가로 입력할 수 있다. 트랜잭션 코드는 마스트에 저장되며, 트랜잭션은 해당 루트 머클 해시를 저장한다. 압축 마스트는 검증 중에 노드 간에 전송해야 하는 데이터의 양과 원장에 저장되는 데이터의 양을 줄인다. 전체 거래 코드를 송신 및 저장하기보다는, 마스트를 통해서만 원하는 경로는 송신 및 저장한다. args 어레이를 사용하여 트랜잭션 코드로 인수를 전달하고 실행할 후속 트랜잭션을 지정하는 것을 지원한다. 또한 거래에는 코드가 유효한지 여부를 확인하는 데 사용되는 관련 금액이 있다. 유효한 거래란 적어도 그 금액의 합만큼 큰 거래를 말한다. 후속 거래 개별 노드가 일련의 트랜잭션을 검증/비검증한 후, 특별한 글로벌 합의노드가 거래의 최종 결과를 결정한다. 합의노드의 과반수가 트랜잭션 세트를 검증하는 경우 트랜잭션은 유효하다. 글로벌 합의노드는 정확한 시스템 상태를 나타내는 글로벌 원장을 [[업데이트]]하고 합의노드는 각 시뮬레이션 체크 시 이 원장과 동기화하여 정확한 상태를 유지한다.

==애플리케이션 및 확장==
===계약 약정===
합의 [[프로토콜]]을 이용하여, 마스트의 공유 계약 작성, 검증 및 실행 기능을 활용하여 다당제 실행 환경을 조성하는 계약 모델화를 실시했다. 이행한 유언비어 계약은 세 당사자 사이의 합의로 이루어졌다. 앨리스, 밥, 캐롤, 트리의 가지는 앨리스의 사망 전후에 승인된 지출을 나타내며, 계약의 조항은 관련 서명자의 서명과 관련하여 특정 조건을 이행할 때 잠금 해제되는 일련의 지점으로 제시한다. 이 구조는 1차 서명자의 하위집합 내에 하청계약이 존재할 수 있도록 하고, 필요한 전제조건이 충족되는 경우로 특정 조항의 집행을 제한하는 동시에 계약 내용의 완전한 투명성을 가능하게 한다. 유언장의 유효한 구성과 실행을 검증하기 위한 합의 프로토콜은 각각 거래의 타당성을 검증하는 [[합의노드]] 그룹을 사용하여 구현되었다.

===압축 코드===
코드 압축을 정량화하는 데 사용된 주요 기준은 일련의 [[파이썬]] [[스크립트]]로, MAST/bin 위치에 있는 당사의 리포(repo)에서 확인할 수 있다. 
파일 longcode.py은 수만 개의 가지를 가진 [[머클트리]]를 생성하여 총 코드 길이가 2M자인데, [[알고리즘]]을 적용한 후의 압축 결과는 23500자 미만이어서 압축률이 90% 이상임을 나타낸다. 그러한 알고리즘은 주파수 기반 압축을 사용하고 롱코드는 반복된 [[세그먼트]]를 반복해서 사용하기 때문에 우리는 우리가 직접 본 코드 압축을 LZW와 같은 다른 알고리즘과 압축하는 것과 비교할 수 없다. 이것은 구조적인 압축을 하므로 괜찮다. 대신 [[리눅스]] 커널에서 코드를 압축하기 위해 zip을 사용하는 것과 비교했다. 이것은 대략 6,115,332자 길이에서 압축률 70%인 1,754,665자까지 걸렸다. 압축 알고리즘은 또한 코드 블록당, 그리고 전체 증명 목록에서도 여러 곳에서 사용될 수 있다는 점에 유의해야 한다. 또한, 우리는 기본적으로 [([subproof], data, mroot)]의 목록인 마스트를 전송하기 위해 최적화되지 않은 메시지 형식을 사용한다. 이것은 문장부호와 화이트스페이스(whitespace)를 사용하지 않고 더 효율적인 문자 인코딩을 사용하도록 더욱 최적화될 수 있다. 놀랍게도 증명을 [[비트코인]] 스크립트로 인코딩하는 것이 외부 검증 스크립트를 갖는 것보다 더 효율적이었다.

==제안 방법==
*'''Johnson Lau의 BIP114''' : 이 기능은 네이티브 [[세그윗]] 주소(bech32)가 마스트의 머클 루트에 커밋할 수 있도록 하는 세그윗 기반 확장 기능을 사용한다. 그런 다음 스펜더는 트리에서 단일 하위 [[스크립트]]를 선택할 수 있다.<ref name="제안">David A. Harding, 〈[https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f What is Bitcoin Merklized Abstract Syntax Tree(MAST)?]〉, 《미디엄》, 2017-10-12</ref> 이 [[BIP]]는 머클트리를 사용하여 스크립트에서 상호 배타적인 분기를 인코딩하는 새로운 미러링 모니터 프로그램 유형을 정의한다. 이는 현재 불가능한 복잡한 상환 조건을 가능하게 하고, 실행되지 않은 스크립트를 숨겨서 프라이버시를 향상시키며, 추가 비용 없이 합의되지 않은 데이터를 포함할 수 있다.<ref name="방법">Alex Lielacher, 〈[https://btcmanager.com/what-is-mast-how-it-improves-bitcoin/ What is MAST and How Does it Improve Bitcoin?]〉, 《BTC매니저》, 2018-03-06</ref>
*'''Mark Friedenbach의 BIP116, 117''' : [[프로그래머]]가 스스로 마스트 기반 반항을 검증할 수 있는 스크립트를 작성할 수 있는 방식으로 스크립트 언어의 유연성을 향상시킨다.  Friedenbach가 선호하는 방식으로 구현할 경우 현재 비트코인(bare, P2SH, 세그윗)이 지원하는 세 종류의 스크립트에 모두 머클 증명을 사용할 수 있게 된다. 두 접근법 모두 서로 비교했을 때 절충을 나타내지만, 두 접근법 모두 공통된 장점이 있다. 어느 쪽이든 [[소프트포크]]로 작동할 수 있다.<ref name="제안"></ref> 첫 번째 BIP는 "스크립트 작성자가 데이터 요소 세트에 커밋하고 전체 세트를 공개하지 않고 구속할 때 이러한 요소 중 하나 이상을 제공할 수 있도록" 하려는 [[BIP116]]이다. 두 번째 BIP는 번호 117이며 제목은 Tail Call Semantics이다. [[프리던배시]](Friedenbach)는 마스트 진술을 달성하는 방법에 관해 설명한다.  "BIP 116과 함께 이 BIP를 사용하면 스크립트가 거의 무제한의 코드 경로에 커밋한 다음 사용 시간에 사용된 실제 코드 경로를 알 수 있다. 이를 통해 복잡한 분기 스크립트를 일련의 비 분기 플랫 실행 경로로 분해하고 가능한 전체 경로 세트를 커밋한 다음 소비 시간에 사용된 경로만 공개할 수 있는 일반화된 마스크 형식을 달성했다."

[[존슨 라우]](Johnson Lau)의 제안은 세그윗 스크립트 내에서만 작동할 수 있지만 프리던배시의 제안은 현재 [[비트코인]] [[블록체인]]에서 사용 중인 3개 스크립트 내에서 구현될 수 있다. 강력하지만 단순한 도구의 모듈성과 구성을 사용하여 마스트를 구성하는 단일 테일 콜 재귀를 통해 합의 코드 변경을 최소화하고 부담을 검토하며 기술 부채를 확보하면서 복잡하고 바람직한 기능을 사용할 수 있다.<ref name="방법"></ref>

==평가 및 전망==
이 프로젝트의 주요 영향은 [[응용 프로그램]]에 있다. 계약을 활용한 기존 환경, 마스트 도입은 기존에 큰 영향을 줄 수 있다. [[비트코인]] 계약에서 [[네트워크]]의 분산 [[노드]] 사이의 코드 전송에 이르는 문제, 이 마스트 구현에 대한 잠재적 개선 사항은 다음과 같다.
*분산 구조 및 실행에 대한 더 큰 지원
*또는 더 큰 확장성을 허용하는 프레임워크 추가
*이 데이터 구조의 사용자에 의해 완벽한 통합
*비트코인은 저장된 데이터의 양을 줄임
*[[블록체인]]을 통해 더 많은 성과를 거둘 수 있게 될 것
*우리가 모델링 한 의지와 같은 복잡한 거래<ref name="제레미 루빈"></ref>

{{각주}}

==참고자료==
* 제레미 루빈, 〈[http://reurl.kr/32844142LX 마스트]〉, 《마스트 백서》
*  Sudhir Khatwani,〈[https://themoneymongers.com/merkelized-abstract-syntax-tree-mast/ Bitcoin's Merkelized Abstract Syntax Tree(MAST) Explained!!]〉, 《TheMoneyMongers》, 2019-08-13
* David A. Harding, 〈[https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f What is Bitcoin Merklized Abstract Syntax Tree(MAST)?]〉, 《미디엄》, 2017-10-12
*  Alex Lielacher, 〈[https://btcmanager.com/what-is-mast-how-it-improves-bitcoin/ What is MAST and How Does it Improve Bitcoin?]〉, 《BTC매니저》, 2018-03-06
*  불곰, 〈[https://brownbears.tistory.com/372 머클트리(merkle tree)란?]〉, 《티스토리》, 2018-07-09
*  〈[https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81_%EA%B5%AC%EB%AC%B8_%ED%8A%B8%EB%A6%AC 추상 구문 트리]〉, 《위키백과》

== 같이 보기 ==
*[[비트코인]]
*[[머클트리]]
*[[AST]]
*[[BIP114]]
*[[BIP116]]
*[[BIP117]]
{{블록체인 기술|검토 필요}}