이국적인 세포

모든 셀에는 -1에서 255 사이의 정수로 인코딩된 고유한 유형이 있습니다. 유형이 -1인 셀은 일반 셀이고, 그 외의 모든 셀은 이색 또는 특수라고 합니다. 이색 셀의 유형은 해당 데이터의 첫 8비트로 저장됩니다. 이색 셀의 데이터 비트가 8비트 미만이면 유효하지 않습니다. 현재 이색 셀 유형은 4가지가 있습니다:

{
  Prunned Branch: 1,
  Library Reference: 2,
  Merkle Proof: 3,
  Merkle Update: 4
}

가지 치기 가지

가지치기된 브랜치는 셀의 삭제된 하위 트리를 나타내는 셀입니다.

레벨 1 <= l <= 3을 가질 수 있으며 정확히 8 + 8 + 256 * l + 16 * l 비트를 포함할 수 있습니다.

첫 바이트는 항상 01 - 셀 유형입니다. 두 번째 바이트는 가지치기된 분기 레벨 마스크입니다. 그 다음에는 삭제된 하위 트리의 l * 32 바이트 해시, 그 다음에는 삭제된 하위 트리의 l * 2 바이트 깊이로 이동합니다.

가지치기된 브랜치 셀의 레벨 l은 브랜치가 가지치기된 구성 중에 외부 머클 증명 또는 머클 업데이트를 결정하기 때문에 De Bruijn 인덱스라고 할 수 있습니다.

가지치기된 브랜치의 더 높은 해시는 해당 데이터에 저장되며 다음과 같이 얻을 수 있습니다:

Hash_i = CellData[2 + (i * 32) : 2 + ((i + 1) * 32)]

라이브러리 참조

라이브러리 참조 셀은 스마트 컨트랙트에서 라이브러리를 사용하는 데 사용됩니다.

항상 레벨 0이며 '8 + 256' 비트를 포함합니다.

첫 바이트는 항상 02 - 셀 유형입니다. 다음 32바이트는 참조하는 라이브러리 셀의 표현 해시입니다.

머클 증명

머클 증명 셀은 셀 트리 데이터의 일부가 전체 트리에 속하는지 확인하는 데 사용됩니다. 이 설계를 사용하면 검증자가 트리의 전체 콘텐츠를 저장하지 않으면서도 루트 해시로 콘텐츠를 검증할 수 있습니다.

머클 증명은 정확히 하나의 참조를 가지며, 그 레벨 0 <= l <= 3은 최대(Lvl(ref) - 1, 0)이어야 합니다. 이 셀은 정확히 8 + 256 + 16 = 280 비트를 포함합니다.

첫 바이트는 항상 03 - 셀 유형입니다. 다음 32바이트는 Hash_1(ref) (또는 참조 수준이 0인 경우 ReprHash(ref))입니다. 다음 2바이트는 참조로 대체된 삭제된 하위 트리의 깊이입니다.

머클 증명 셀의 상위 해시 '해시_i'는 일반 셀의 상위 해시와 유사하게 계산되지만, '해시_i(ref) 대신 '해시_i+1(ref)가 사용됩니다.

머클 업데이트

머클 업데이트 셀은 항상 2개의 참조를 가지며 두 개의 참조 모두에 대해 머클 증명처럼 작동합니다.

머클 업데이트 레벨 0 <= l <= 3은 최대(Lvl(ref1) - 1, Lvl(ref2) - 1, 0)입니다. 정확히 8 + 256 + 256 + 16 + 16 = 552 비트를 포함합니다.

첫 바이트는 항상 04 - 셀 유형입니다. 다음 64바이트는 이전 해시와 새 해시라고 불리는 Hash_1(ref1)과 Hash_2(ref2)입니다. 그 다음 4바이트는 삭제된 이전 하위 트리와 삭제된 새 하위 트리의 실제 깊이입니다.

간단한 증명 확인 예시

셀 c가 있다고 가정해 보겠습니다:

24[000078] -> {
    32[0000000F] -> {
        1[80] -> {
            32[0000000E]
        },
        1[00] -> {
            32[0000000C]
        }
    },
    16[000B] -> {
        4[80] -> {
            267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],
            512[00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000064]
        }
    }
}

하지만 우리는 그 해시 44efd0fdfffa8f152339a0191de1e1c5901fdcfe13798af443640af99616b977만 알고 있습니다, 셀 a 267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040]는 전체 c를 받지 않고 실제로 c의 일부임을 증명하고 싶습니다. 따라서 우리는 증명자에게 관심 없는 모든 가지를 가지치기된 가지 셀로 대체하는 머클 증명을 생성하도록 요청합니다.

ㄱ'에 도달할 방법이 없는 첫 번째 c 자손은 ref1입니다:

32[0000000F] -> {
    1[80] -> {
        32[0000000E]
    },
    1[00] -> {
        32[0000000C]
    }
}

따라서 증명자는 해시(ec7c1379618703592804d3a33f7e120cebe946fa78a6775f6ee2e28d80ddb7dc)를 계산하고 가지치기 브랜치 288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28d80DDB7DC0002]를 생성하고 ref1를 이 가지치기로 대체합니다.

두 번째는 512[0000000...00000000064]이므로 증명자는 이 셀도 대체하기 위해 Pruned 브랜치를 생성합니다:

24[000078] -> {
    288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28D80DDB7DC0002],
    16[000B] -> {
        4[80] -> {
            267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],
            288[0101A458B8C0DC516A9B137D99B701BB60FE25F41F5ACFF2A54A2CA4936688880E640000]
        }
    }
}

증명자가 검증자(이 예에서는 저희)에게 보내는 머클 증명 결과는 다음과 같습니다:

280[0344EFD0FDFFFA8F152339A0191DE1E1C5901FDCFE13798AF443640AF99616B9770003] -> {
    24[000078] -> {
        288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28D80DDB7DC0002],
        16[000B] -> {
            4[80] -> {
                267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],
                288[0101A458B8C0DC516A9B137D99B701BB60FE25F41F5ACFF2A54A2CA4936688880E640000]
            }
        }
    }
}

우리(검증자)는 증명 셀을 가져올 때 해당 데이터에 c 해시가 포함되어 있는지 확인한 다음 유일한 증명 참조에서 Hash_1을 계산합니다: 44efd0fdfffa8f152339a0191de1e1c5901fdcfe13798af443640af99616b977을 계산하여 c` 해시와 비교합니다.

이제 해시가 일치하는지 확인했으면 셀 깊숙이 들어가서 (우리가 관심 있는) 셀 a가 있는지 확인해야 합니다.

이러한 증명은 반복적으로 계산 부하와 검증자에게 전송하거나 저장해야 하는 데이터의 양을 줄여줍니다.

참고 항목

고급 증명 검증 예시

이국적인 세포

가지 치기 가지​

라이브러리 참조​

머클 증명​

머클 업데이트​

간단한 증명 확인 예시​

참고 항목​