Bitcoin Merkelized Abstract Syntax Tree가 무엇인지 알아보십시오.
원래 제목: "Dry goods | Bitcoin Merkelization Abstract Syntax Tree는 무엇입니까? ", 데이비드 A. 하딩
Merklized Abstract Syntax Trees(MAST)는 더 작은 트랜잭션 크기, 더 나은 개인 정보 보호 및 더 큰 스마트 계약을 가능하게 하는 비트코인에 대해 제안된 업그레이드입니다. 이 기사에서는 MAST의 이론적 근거를 설명하고 잠재적인 이점을 설명하며 이 기술을 통합하는 현재 제안을 요약합니다.
문제: 사용하지 않는 스크립트 데이터
Satoshi Nakamoto는 Bitcoin 백서에 작성하지 않은 흥미로운 기능을 Bitcoin에 제공했습니다. 공개 키를 통해 비트코인을 받고 개인 키 디지털 서명으로 비트코인을 사용하는 것 외에도 사용자는 동적 공개 키 및 서명으로 사용할 수 있는 프로그램("스크립트"라고 함)을 작성할 수도 있습니다.
모든 비트코인 지갑의 기본 작업인 스크립트를 지정할 때 비트코인 네트워크에 의해 시행되는 비트코인 프로토콜은 스크립트가 True를 반환하지 않는 한 누구도 스크립트에 의해 제어되는 비트코인을 사용하는 것을 허용하지 않습니다. 이를 통해 개인 키로 서명하기 위해 거래를 요구하는 것과 같이 "저당권"(속성 조건)이라고 하는 자금을 사용할 수 있는 조건을 지정할 수 있습니다.
이 기사 전체에서 사용할 다음 예와 같이 더 복잡한 속성 조건도 가능합니다. Alice는 언제든지 비트코인을 사용할 수 있기를 원하지만 연속 3개월 동안 비트코인을 사용하지 않으면 또는 무능력), 그녀는 형제자매인 밥과 찰리가 비트코인을 소유하고 동의할 수 있는 곳이면 어디에서나 사용하기를 원합니다.
다음 조건부 스크립트는 위의 목표를 달성하고 Alice의 공개 키(개인 키의 서명을 확인해야 함)를 포함할 뿐만 아니라 제한 시간 조건, Bob과 Charlie의 공개 키와 같은 조건 논리를 추가합니다.
현재 비트코인 프로토콜에서는 위에서 언급한 모든 데이터를 블록체인에 추가해야 하며, 앨리스의 비트코인이 소비될 때 특정 소비 행태와 전혀 관련이 없는 스크립트 부분도 포함되어 있기 때문에 이 부분도 반드시 노출되어야 합니다. 예를 들어 Alice가 비트코인을 사용하면 Bob과 Charlie의 공개 키도 노출됩니다.
사용되지 않은 조건부 데이터는 트랜잭션의 크기를 증가시키고 사용자를 필요 이상으로 더 많은 개인 정보에 노출시키는 동시에 스마트 계약 크기의 주요 제한 요소인 확인 비용보다 크기를 만듭니다. MAST는 스크립트의 미사용 부분을 블록체인에 직접 포함할 필요를 제거하여 이러한 상황을 개선하는 것을 목표로 합니다.
MAST 초기 아이디어
MAST 1의 기본 아이디어는 두 가지 오랜 개념인 추상적 시맨틱 트리와 머클 트리에서 나옵니다. AST(Abstract Semantic Tree)는 프로그램을 독립적인 작은 조각으로 나누어 프로그램을 설명하는 방법으로, 프로그램을 보다 쉽게 분석하고 최적화할 수 있습니다. AST를 생성하려면 모든 전제를 찾을 때까지 모든 방정식을 화살표로 전제와 연결해야 합니다. 아래 그림은 위 예제 스크립트의 AST입니다.
반면에 Merkle 트리는 집합의 전체 그림을 알지 못한 채 요소가 집합에 속하는지 여부를 확인하는 데 사용할 수 있습니다. 예를 들어 비트코인의 SPV 지갑(Simple Payment Verification Wallet)은 머클 트리를 사용하여 특정 블록에 특정 트랜잭션이 존재하는지 여부를 확인하므로 전체 블록을 다운로드할 필요가 없어 대역폭을 절약할 수 있습니다.
Merkle 트리를 생성하려면 먼저 각 요소를 한 번 해시하여 고유한 식별자를 생성한 다음 이러한 식별자를 쌍으로 만들고 다시 해시하여 식별자 쌍의 식별자를 생성하는 식으로 하나의 식별자만 남을 때까지 반복합니다. 전체 세트를 표시하는 짧은 식별자인 "메르켈 루트".
요소가 집합에 속하는지 확인할 때 전체 집합을 소유한 사람이 해당 요소에서 Merkle 루트까지의 경로에 있는 모든 식별자를 제공할 수 있습니다. 이것은 요소가 실제로 집합에 있음을 증명합니다.
요컨대, AST 이면의 기술을 통해 프로그램을 작은 조각으로 나눌 수 있고 머클 트리를 통해 전체 프로그램을 노출하지 않고도 이러한 작은 조각이 실제로 완전한 프로그램의 일부인지 확인할 수 있습니다. 이것이 MAST의 기본 원칙으로 소비자가 단일 트랜잭션에서 사용되지 않는 조건을 Merkle 증명으로 대체할 수 있도록 하여 트랜잭션 크기를 줄이고 개인 정보 보호를 개선하며 더 큰 계약을 지원합니다.
MAST의 예
위의 속성 조건을 예로 들어 우리가 원하는 두 가지 가능한 시나리오에 대해 두 개의 첨자로 나눕니다.
Alice는 언제든지 비트코인을 사용할 수 있습니다(왼쪽 아래 첨자).
또는 Alice의 서명을 사용하여 연속 3개월 동안 지출하는 경우 Bob과 Charlie의 서명이 비트코인을 지출해야 합니다(아래 그림 오른쪽 아래 첨자).
다음 두 개의 별도 첨자를 기반으로 Merkle 트리를 생성합니다.
이 Merkle 트리의 루트는 최종적으로 Alice의 완전한 속성 조건을 식별하며 크기는 32바이트에 불과합니다. 그런 다음 Alice는 대체 조건부 스크립트를 사용하여 지출 거래는 첨자 중 하나가 Merkle 루트에 연결되어 있다는 증거가 제공되고 서브루틴이 True를 반환하는 경우에만 유효하다고 명시할 수 있습니다.
아래 첨자의 Merkle 증명은 어떤 첨자를 사용하느냐에 따라 다음 그림과 같이 시각적으로 그려집니다.
이점 #1 - 소액 거래
먼저 MAST가 복잡한 속성 조건을 가진 사용자가 더 작은 트랜잭션을 생성할 수 있도록 하는 방법을 살펴보겠습니다. 이것이 MAST가 우리에게 가져다주는 첫 번째 이점입니다.
위의 예에서 우리는 아래 첨자가 두 개인 속성 표시줄을 사용했습니다. Alice가 자신의 돈을 쓰거나 Bob과 Charlie가 3개월을 기다린 후 함께 돈을 씁니다. 세 번째 첨자는 3개월 1일 후에 Dan과 Edith가 자금을 사용할 수 있다고 지정하고, 4번째 첨자는 3개월 2일 후에 Fred와 George가 자금을 사용할 수 있다고 지정하는 등의 무한 확장 버전을 상상해 봅시다. .
이 사고 실험은 MAST 유무에 관계없이 아래 첨자 수와 블록에 추가해야 하는 조건부 데이터 양 사이의 관계를 보여주는 아래 그래프로 이어집니다.
다음은 동일한 의미를 갖는 로그 도표입니다.
MAST 트랜잭션의 크기는 우리의 두 서브 스크립트의 조건과 같이 처음에 MAST가 없는 동일한 조건 트랜잭션보다 크지만 비 MAST 트랜잭션 크기는 선형적으로 증가합니다(서브 스크립트의 수와 함께). , 반면 MAST 거래량은 대수적으로만 증가합니다.
데이터 볼륨을 절약하는 것이 주요 목표인 경우 추가로 최적화할 수 있습니다. 많은 부동산 조건에서 소비자는 그 중 하나를 더 자주 사용할 수 있습니다. 예를 들어 Alice는 장수하기를 원하기 때문에 그녀가 구성하는 Merkle 트리는 그녀의 지출 조건을 상단에 더 가깝게 배치하고 다른 모든 조건은 트리 하단에 배치합니다.
Alice가 자금을 사용할 때 거래 데이터의 양은 자신의 재산 상태에 수혜자가 몇 명이든 관계없이 항상 최적의 상황이며, 그녀의 수혜자가 자금을 사용할 때 거래 데이터의 양 또한 최적의 상황임을 알 수 있습니다. 앞서 언급한 표준 구성 Merkle 트리보다 몇 바이트 더 많을 뿐입니다.
Alice가 어떤 배열을 선택하든 MAST는 다중 첨자 속성 조건부 트랜잭션을 더 작게 만들 수 있으므로 사용자는 더 적은 비용을 지불하고 더 많은 고급 트랜잭션을 블록에 로드할 수 있습니다.
이점 #2 - 개인 정보 보호 강화
위의 설명에서 우리는 Alice의 속성 스크립트를 모두 노출했지만 Alice가 자신의 비트코인을 사용하는 경우 블록체인에서 아래 그림의 왼쪽에 있는 데이터만 볼 수 있다고 상상할 수 있습니다.
이 정보만으로는 Alice 이외의 사람이 여기에서 자금을 사용할 수 있는지 여부와 지출 시 직면해야 하는 제약 사항을 알 수 없습니다. MAST에서 다른 조건이 있을 수 있다고 추측할 수 있지만 그것은 단지 추측일 뿐입니다. Alice는 Merkle 트리에 다른 소비 가능한 부분이 있는 것처럼 가장할 수 있습니다.
이에 따라 다른 지점(즉, 위 그림의 오른쪽 아래 첨자)이 보이면 타임아웃 전에 자금을 사용할 수 있는지 여부를 알 수 없으며, 개인 키만 사용할 수 있습니다. 다른 지출 조건이 있다고 추측할 수도 있지만 블록체인에서 이를 확인할 수는 없습니다.
사용하지 않는 부동산 상태가 노출되지 않도록 하는 것은 매우 유용합니다.예를 들어 일부 상인은 스마트 계약이 가능한 한 기밀로 유지되고 잠재적인 경쟁자에게 표시되지 않기를 원할 수 있습니다. 이것은 스마트 계약을 위해 설계되었다고 주장하지만 실제로는 이러한 계약에 대한 프라이버시를 제공할 수 없는 일부 알트코인과 대조됩니다.
프라이버시는 또한 일부 사용자가 단순히 재산 측면에서 프라이버시에 관심이 없더라도 모든 비트코인 사용자에게 추가적인 이점을 제공할 수 있습니다. 이 기사의 처음부터 Alice가 비 MAST 조건 템플릿을 사용하는 유일한 사람이라고 가정합니다. 모든 조건이 공개되기 때문에 누구나 Alice의 지출 행동을 추적할 수 있습니다. 블록체인에서 이 템플릿의 사용을 관찰하기만 하면 Alice의 개인 정보가 사라집니다.
특정 사용자를 쉽게 식별할 수 있는 모든 디자인은 사람들이 자신의 비트코인을 다른 사람의 비트코인과 다르게 취급하는 것을 더 쉽게 만들 것입니다. 이를 "동질성 부족"이라고 합니다. Alice의 재산 상태가 어떤지 아는 사람이 있으면 뇌물을 주거나 광부에게 이러한 사람들의 거래를 포장하지 않도록 강요하여 Alice가 자신의 비트코인을 사용하지 못하도록 할 수 있습니다.
MAST는 이 문제를 완전히 해결할 수 없습니다. 앨리스(또는 밥과 찰리)는 여전히 일부 방해 요소를 밝혀야 하기 때문입니다.
예를 들어 Alice의 기본 지출 행동은 단일 서명만 제공하면 되는 다른 일반적인 지불 행동처럼 보이므로 Alice의 MAST 기반 거래는 다른 MAST 기반 단일 서명 거래와 다르지 않습니다. 이는 MAST 기반 단일 서명 조건을 사용하는 모든 사용자의 금전적 동질성과 자금의 동질성뿐만 아니라 Alice의 개인 정보 보호를 향상시킵니다.
MAST의 이러한 이점은 Bitcoin의 개인 정보 보호 및 동질성을 개선하기 위한 다른 제안과 결합될 가능성이 있습니다. Pieter Wuille 및 Gregory Maxwell의 "Universal Threshold Tree", Andrew Poelstra의 "Scriptless Script" 및 Thaddeus Dryja의 "Discrete Logarithm Contract"와 같이 단일 서명으로 특정 복합 속성 조건을 사용할 수 있도록 하는 제안이 있습니다. MAST는 이들과 결합할 수 있습니다. 체계.
그러나 이러한 솔루션 중 어느 것도 Bitcoin에서 구현할 수 없더라도 MAST 자체는 복잡한 속성 조건을 가진 사용자에게 더 많은 개인 정보 보호 및 호환성을 제공할 수 있습니다.
이점 #3 - 더 큰 스마트 계약
비트코인은 이제 개별 스크립트에 대해 세 가지 다른 크기 제한을 설정합니다: 2010년 7월에 도입된 네이키드 스크립트는 크기가 10,000바이트를 초과할 수 없으며, P2SH 스크립트는 520바이트를 초과할 수 없으며, segwit 스크립트는 10,000바이트를 초과할 수 없습니다. 위의 그림에서 이러한 크기를 보여줍니다.
극단적인 무한 확장의 경우에도 MAST는 현재의 모든 메커니즘보다 더 많은 조건부 분기를 지원한다는 것을 알 수 있습니다. 사실 MAST의 확장성은 관측 가능한 우주에 모든 에너지가 있어도 표준(균형 잡힌) Merkle 트리를 만드는 데만 사용한다면 그 Merkle 증거는 8448바이트에 불과합니다. 이렇게 큰 Merkle 증명의 경우에도 최신 노트북은 1밀리초 이내에 이를 확인할 수 있습니다.
MAST는 또한 비트코인 스크립트가 미사용 첨자를 처리하는 작업에서 전체 노드를 해제하여 다른 엄격한 제한을 우회하도록 도울 수 있습니다. 이와 관련하여 MAST는 Bitcoin 스마트 계약의 장기 설계 목표를 잘 보존하고 확장했습니다. 메모리 및 처리 능력, 하지만 보상할 수 없으므로 가능한 한 적게 책임을 져야 합니다.
따라서 MAST의 진정한 성과는 비트코인 사용자가 (그 어느 때보다) 더 발전된 계약을 생성하도록 허용하는 것이 아니라 비트코인 노드에 새로운 부담을 추가하지 않고 이러한 가능성을 열어주는 것입니다.
MAST 구현: 기존의 여러 제안
지금까지 비트코인 프로토콜에서 MAST를 활성화하는 두 가지 방법이 bitcoin-dev 메일링 리스트에 제안되었으며, 둘 다 아직 초안 단계에 있으며 변경될 수 있습니다.
첫 번째 제안은 Johnson Lau(가명 "jl2012")가 제안한 BIP114로, 원래의 분리된 증인 주소(bech32)가 MAST 속성 조건에 대한 Merkle 루트 커밋이 될 수 있도록 분리된 증인에 기반한 확장 기능을 사용합니다. 따라서 지출 트랜잭션은 트리에서 하위 스크립트를 선택할 수 있습니다.
두 번째 제안인 Mark Friedenbach(별칭 "maaku")의 이름 없는 두 BIP(1, 2)는 스크립팅 언어의 유연성을 높여 프로그래머가 스크립트를 작성하여 MAST 기반 속성 조건을 확인할 수 있도록 합니다. Friedenbach가 선호하는 방식으로 구현되어 비트코인이 현재 지원하는 세 가지 스크립트 유형(네이키드 스크립트, P2SH 및 분리된 증인 스크립트) 모두에서 Merkle 증명을 사용할 수 있습니다.
이러한 몇 가지 제안은 각각 장단점이 있지만 모두 위에서 언급한 MAST의 이점을 제공합니다(바이트 수는 늘리거나 줄일 수 있음). 각각은 소프트 포크로 활성화할 수 있습니다.
결론: 언제 MAST를 사용할 수 있습니까?
위에서 MAST의 장점에 대해 설명하고 비트코인에서 MAST를 구현하기 위한 두 가지 제안을 간략하게 언급했습니다. 슬프게도 저도 모릅니다.
아이디어에서 제안, 완전한 구현, 소프트 포크 제안, 소프트 포크 활성화에 이르기까지 길은 길고 어렵습니다. 이것은 분리된 증인 업그레이드를 둘러싼 2년 간의 드라마에 의해 충분히 분명해졌습니다.
하지만 내 관점에서 볼 때 MAST의 기본 아이디어는 비트코인 기술 커뮤니티에서 폭넓은 지지를 얻었고 MAST에 가장 관심을 가진 개발자들은 이 기술이 완전히 신뢰할 수 없다는 것을 누군가가 증명하지 않는 한 계속해서 개발할 것입니다. 이 개발자들이 동료 검토 가능한 소프트 포크 코드를 성공적으로 제안하면 MAST가 비트코인 프로토콜의 일부가 될 수 있는지 여부를 결정하는 것은 독자와 다른 비트코인 사용자에게 달려 있습니다.
감사합니다
BIP114: Merklized Abstract Syntax Tree by Johnson Lau
Tail Call Sematics by Mark Friedenbach
MerkleBranchVerify opcode by Mark Friedenbach
Discussion at core.tech meetup by Mark Friedenbach (transcribed by Bryan Bishop)
Merklized Abstract Syntax Trees by Jeremy Rubin, Manali Naik, Nitya Subramanian
An explanation and justification of the tail-call and MBV approach to MAST by Mark Friedenbach
Making MAST Meaningful by Brian Deery
The next step to improve Bitcoin by Aaron van Wirdum
감사합니다
각주
각주
Russell O'Connor는 MAST의 프로토타입을 처음으로 설명했으며 일부 출처에는 Pieter Wuille이 추가되었습니다. 출처: Peter Todd, Gregory Maxwell(Jeremy Rubin 등에서 인용), Mark Friedenbach(개인 커뮤니케이션).
고마워 존 뉴베리.
원본 링크:
(위에)
(이 기사에는 많은 하이퍼링크가 있습니다. 왼쪽 하단의 "원문 읽기"를 클릭하면 EthFans 웹 사이트에서 가져올 수 있습니다.)
원본 링크:
https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
번역: 아지안
번역: 아지안
