Verkle 트리는 Merkle 트리와 유사하게 작동하지만 훨씬 더 작은 목격자가 있는 확약 체계입니다. Merkle 트리의 해시를 벡터 커밋으로 대체하여 작동하므로 더 넓은 분기 요소가 더 효율적입니다.
게시물에 대한 피드백을 주신 Kevaundray Wedderburn에게 감사드립니다.
버클 트리의 작동 방식에 대한 자세한 내용은 다음을 참조하세요.
이 포스트의 목적은 Draft verkle tree EIP의 구체적인 레이아웃을 설명하는 것입니다. verkle tree를 구현하고자 하며 EIP에 대해 더 깊이 파고들기 전에 소개를 원하는 클라이언트 개발자를 대상으로 합니다.
Verkle 트리는 트리 구조에 여러 변경 사항을 도입합니다. 가장 중요한 변경 사항은 다음과 같습니다.
verkle 트리에 대한 벡터 약정 체계로 Pedersen 약정을 사용합니다. . Pedersen 약정은 타원 곡선을 기반으로 합니다. Pedersen 약정에 대한 소개와 이를 Inner Product Arguments를 사용하여 다항식 또는 벡터 약정으로 사용하는 방법은 여기를 참조하십시오.
우리가 사용하는 곡선은 Bandersnatch입니다. 이 곡선은 성능이 뛰어나고 BLS12_381의 효율적인 SNARK가 향후 verkle 트리에 대해 추론할 수 있기 때문에 선택되었습니다. 이는 롤업에 유용할 뿐만 아니라 추가 확약 업데이트 없이 모든 증인을 하나의 SNARK로 압축할 수 있는 업그레이드를 허용하는 데 유용할 수 있습니다.
bandersnatch의 곡선 차수/스칼라 필드 크기는 p =13108968793781547619861935127046491459309155893440570251786403306729687672801입니다. , 253비트 소수입니다. 결과적으로 최대 252비트의 비트 문자열에만 안전하게 커밋할 수 있습니다. 그렇지 않으면 필드가 오버플로됩니다. 우리는 verkle 트리에 대해 256의 분기 인수(너비)를 선택했습니다. 이는 각 커밋이 각각 252비트의 값(정확하게는 p - 1까지의 정수)을 최대 256개까지 커밋할 수 있음을 의미합니다. ). 이것을 Commit(v₀, v₁, …, v₂₅₅)으로 씁니다. 목록 v에 커밋 길이 256.
verkle tree EIP의 설계 목표 중 하나는 인접 위치(예:거의 동일한 주소 또는 인접 코드 청크가 있는 저장소)에 대한 액세스를 저렴하게 만드는 것입니다. 이를 위해 키는 줄기로 구성됩니다. 31바이트 및 접미사 총 32바이트에 대해 1바이트입니다. 키 구성표는 "닫힌" 저장 위치가 동일한 줄기와 다른 접미사에 매핑되도록 설계되었습니다. 자세한 내용은 EIP 초안을 참조하십시오.
verkle 트리 자체는 두 가지 유형의 노드로 구성됩니다.
확장 노드에 대한 커밋은 4개 요소 벡터에 대한 커밋입니다. 나머지 위치는 0입니다. 다음과 같습니다.
C₁ 및 C₂는 stem과 동일한 스템을 가진 모든 값에 커밋하는 두 가지 추가 커밋입니다. . 커밋이 필요한 이유는 값이 32바이트이지만 필드 요소당 252비트만 저장할 수 있기 때문입니다. 따라서 단일 약정은 256개의 값을 저장하기에 충분하지 않습니다. 따라서 대신 C₁는 접미사 0에서 127에 대한 값을 저장하고 C₂는 128에서 255를 저장합니다. 여기서 값은 필드 크기에 맞추기 위해 두 개로 분할됩니다(나중에 설명하겠습니다.)
약정 C₁ 및 C₂와 함께 확장을 "확장 및 접미사 트리"(줄여서 EaS)라고 합니다.
그림 1 0xfe0002abcd..ff04 키에 대한 버클 트리를 통한 걷기 표현 :경로는 각각 256개의 자식(254, 0, 2)이 있는 3개의 내부 노드를 통과하며, 하나의 확장 노드는 abcd..ff를 나타냅니다. 04 값을 포함한 두 개의 접미사 트리 약정 , v₄. 줄기 실제로 내부 노드를 통한 경로를 포함하여 키의 처음 31바이트입니다.
각 확장 및 접미사 트리 노드에는 256개의 값이 있습니다. 값의 너비가 256비트이고 한 필드 요소에 252비트만 안전하게 저장할 수 있기 때문에 단순히 한 필드 요소에 하나의 값을 저장하려고 하면 4비트가 손실됩니다.
이 문제를 피하기 위해 256개 값 그룹을 각각 128개 값으로 구성된 두 그룹으로 분할하기로 결정했습니다. 그룹의 각 32바이트 값은 2개의 16바이트 값으로 분할됩니다. 따라서 V ++ Võ =Võ
값을 VV ∈ 𝔹₁₆ 𝔹₁₆ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₁₆ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 𝔹₃₂ 으로 바꿉니다.v⁽ˡᵒʷᵉʳ⁾ᵢ에 "리프 마커"가 추가되어 액세스한 적이 없는 리프와 0으로 덮어쓴 리프를 구분합니다. 버클 트리에서 삭제되는 값은 없습니다. . 이것은 다가오는 상태 만료 계획에 필요합니다. 그 마커는 129 번째 비트에서 설정됩니다. 즉, Võ가 이전에 액세스 한 경우 Võ =v³ + 2 ²입니다.
두 개의 약정 C₁ 및 C₂는 다음과 같이 정의됩니다.
확장 노드에 대한 커밋은 숫자 1인 "확장 마커", 두 개의 하위 트리 커밋 C₁ 및 C₂ 및 줄기로 구성됩니다. 이 확장 노드로 연결되는 키입니다.
부모 내부 노드를 자식 내부 노드로 연결하는 키 섹션만 포함하는 Merkle-Patricia 트리의 확장 노드와 달리 스템은 해당 지점까지 전체 키를 덮습니다. 이는 verkle 트리가 stateless 증명을 염두에 두고 설계되었기 때문입니다. 확장을 둘로 "분할"하는 새 키가 삽입되면 더 작은 증명을 허용하는 이전 형제를 업데이트할 필요가 없습니다.
내부 노드는 커밋에 대해 더 간단한 계산 방법을 사용합니다. 노드는 256개 하위 트리 각각의 루트 커밋(필드 표현)인 256개 값의 벡터로 표시됩니다. 빈 하위 트리에 대한 커밋은 0입니다. 하위 트리가 비어 있지 않으면 내부 노드에 대한 커밋은
입니다.
여기서 Cᵢ은 내부 노드의 자식이고 자식이 비어 있으면 0입니다.
그림 2는 새로운 값을 트리에 삽입하는 과정을 보여주는 그림으로, 여러 초기 바이트에서 줄기가 충돌할 때 흥미로워집니다.
그림 2 값 v₁₉₂는 0000010000...0000 위치에 삽입됩니다. 0000000000...0000 위치의 v₁₂₇ 값만 포함하는 verkle 트리에서 . 줄기는 세 번째 바이트에서 다르기 때문에 다른 바이트까지 두 개의 내부 노드가 추가됩니다. 그런 다음 전체 31바이트 줄기가 있는 또 다른 "확장 및 접미사" 트리가 삽입됩니다. 초기 노드는 그대로이고 C²₀는 삽입 전의 C⁰₀와 같은 값을 가집니다.
verkle 트리 구조는 더 얕은 트리를 만들어 저장 데이터의 양을 줄입니다. 그러나 그것의 진정한 힘은 더 작은 증거, 즉 증인을 생산하는 능력에서 나옵니다. 이것은 다음 기사에서 설명할 것입니다.