BAF라는 아이디어는 토니의 BAL에 대한 훌륭한 연구에서 영감을 받았습니다. 사실 저는 그의 글에 대한 답글로 이 아이디어를 처음 게시했습니다. 아래에서 이 아이디어를 더 자세히 설명해 보겠습니다.
이 게시물은 완성된 디자인이라기보다는 브레인덤프라고 생각해 주세요.
슬롯 타임은 네트워크의 상태 변화를 확산하는 데 걸리는 시간에 따라 명백히 제한됩니다. 왜냐하면 다음 블록 생성자는 변경에 대한 정보를 필요로 하기 때문입니다. 블록 (실행될 트랜잭션 목록) 형태이든 밸런서(BAL) (상태 변경 집합) 형태이든, 이는 전 세계로 상당한 양의 데이터를 전송해야 함을 의미합니다.
이러한 종속성은 종종 네트워크 지연 시간에 대한 가상의 \Delta Δ 상한값으로 우아하게 모델링됩니다. 그러나 실제로 네트워크 지연 시간은 확산될 정보의 크기에 따라 달라집니다.
실제 블록 도착하기 훨씬 전에 다음 블록 의 준비를 시작할 수 있을 만큼 적은 양 의 정보를 처리 할 수 있다면 어떨까요?
BAF는 바로 이러한 목적을 달성하는 것을 목표로 합니다. BAF는 블록 i에서 접근하지 않은 상태 S의 부분 S'을 식별하는 작은 블룸 필터입니다. 따라서 블록 i를 모르더라도 S'에 대한 모든 연산은 블록 i+1에서 안전하게 수행할 수 있습니다.
하지만 블룸 필터는 "느슨"한데, 어떻게 작동할 수 있을까요?
밸런서(BAL) (사용하는 밸런서(BAL) 유형에 대한 자세한 내용은 추후 설명)을 블룸 필터를 사용하여 압축하여 BAF를 구합니다. 그런 다음, 블록 i에 의해 "손상되지 않은"(접근되지 않은) 상태의 e 사용합니다.
블룸 필터는 손실 압축으로 볼 수 있습니다. 블룸 필터는 크기가 고정되어 있으며, 다음과 같은 특징이 있습니다.
- False Positives(FP)가 있습니다. 우리는 일부
e액세스되었다고 생각하지만 실제로는 액세스되지 않았습니다. - 거짓 부정(FN)이 없습니다. 우리는 일부 상태
e접근하지 못했다고 생각하지만 실제로는 접근했습니다.
블룸 필터가 정확하지는 않지만, 부정 방식으로 사용하면 문제가 되지 않습니다. 블룸 필터 때문에 너무 많은 요소를 제외할 수 있지만, 블록 i에 의해 수정된 요소는 절대 포함하지 않습니다(그것이 블룸 필터가 될 것이기 때문입니다).
이 필터가 작을 수 있나요?
현재 평균 비압축 밸런서(BAL) 크기는 55KB이며 , 각 항목의 길이는 32 + 20 = 52바이트입니다 . 즉, 약 1,000개의 항목이 있습니다.
IP 패킷에 쉽게 들어갈 수 있는 1KB 블룸 필터를 사용한다고 가정해 보겠습니다. 8196 비츠(Bits), 블룸 필터로서는 상당히 큰 공간입니다. 블룸 필터는 k개의 해시 함수로 정의되며, 각 함수는 요소를 8196개 중 하나의 위치에 매핑합니다. 블룸 필터에 요소를 추가할 때, 이 비츠(Bits) (이미 켜져 있지 않다면) 켜집니다. 요소를 검사할 때, 이 비츠(Bits) 중 하나라도 0이면 해당 요소가 추가되지 않았음을 확인할 수 있습니다.
해시 함수의 이상적인 개수는 다음과 같이 정의됩니다.
그러면 FP 확률은 다음과 같이 추정할 수 있습니다.
이 BAF를 사용하는 사람은 블록 이나 밸런서(BAL) 없더라도 주어진 거래가 다른 블록 에 잠재적으로 간섭할 수 있는지 확인하고, 간섭할 수 없는지 확실하게 말할 수 있습니다.
BAF의 내용과 세부성은 어떠해야 합니까?
여기에는 다양한 디자인 옵션이 있습니다.
- 계정 수준 세분성 대 슬롯 수준 세분성
- 상태 접근 대 상태 수정
계정 대 슬롯 세분성
상태 접근의 경우, 계정 수준과 슬롯 수준 모두 세분성이 적합할 수 있습니다. 계정 수준은 필터가 더 빈약하지만 더 구조적인 배제를 의미하고, 슬롯 수준은 배제가 적지만 필터가 더 포화되어 더 높은 FP 비율을 의미합니다. 위의 2% 추정치는 후자를 기준으로 합니다.
논스 충돌을 피하기 위해 거래 발신자에 대한 계정 수준 제외도 필요합니다.
흥미로운 점은 필요하다면 이진 OR을 사용하여 두 가지 다른 세분성을 동일한 필터에 쉽게 결합할 수 있으며, 동일한 비트맵에 계정 수준 거래 발신자와 슬롯 수준 상태 액세스 정보를 모두 추가할 수 있다는 것입니다.
국가 접근 대 국가 수정
정의에 따르면 상태 액세스 수준 BAF는 상태 수정 수준 필터(이하 BMF라고 함)보다 더 포화 상태(1이 더 많음)입니다.
비엠에프
BMF를 사용하여 빌더가 블록 준비를 시작할 수 있도록 도울 수 있습니다. BMF가 슬롯 시간의 극히 짧은 부분(예: 300ms) 안에 다음 블록 빌더에 도달할 수 있다고 가정하면, 이전 블록에 의존하지 않는 블록 의 일부를 준비하는 데 사용할 수 있습니다.
BMF는 슬롯 시간을 단축하고 블록 순서가 충돌 없이 유지되도록 하는 데 유용할 수 있습니다. 블록 i의 BMF를 알면 블록 i+1을 생성하는 개발자는 블록 i-1과 블록 i 사이의 변경 불가능한 상태를 기반으로 블록을 생성할 수 있습니다. 이를 통해 마지막 순간에 블록 을 블록 i에 기반할지, 아니면 블록 i-1에 기반할지 결정할 수 있습니다.
바프
BAF는 결국 병렬 블록 구축에 유용할 수 있습니다. 빌더가 다른 블록 의 BAF를 존중한다면, 두 블록은 최종적으로 체인으로 시퀀싱될 때 병렬화 가능해지거나, 다시 말해 순서에 구애받지 않게 됩니다.
BAF(또는 BMF) 보안
서명: BAF는 블록 생성자 에 의해 서명되고 시행될 수 있습니다.
엄격함: 서명하고 적용하면 BAF가 정확해야 한다는 요구 사항을 만들 수 있으며 재실행 중에 생성되는 필터보다 더 많은 것을 요구하지 않습니다.
BAF 가격 책정
단순히 많은 상태에 접근하는 트랜잭션이 있어 밸런서(BAL)( Best Algorithm Algorithm)이 커지고 BAF(Balanced Functions AF)가 포화되는 경우가 있습니다. 이러한 트랜잭션은 BMF 기반 사전 빌드 및 BAF 기반 병렬화의 가능성을 크게 줄입니다.
BAF(Battery Air Force)를 완전히 갖추는 데 비용을 많이 들이는 게 합리적일까요? 이게 옳은 생각인지는 잘 모르겠지만, 디자인 측면에서는 고려해 볼 만합니다.
불운한 콤보
확률적 필터이기 때문에, 접근된(또는 수정된) 상태가 그다지 크지 않더라도 일부 조합에서 BAF가 포화될 수 있습니다. 이는 블룸 필터의 비츠(Bits) 구성하는 해시 함수의 불운한 조합입니다.
"회전" 블룸 필터 구조를 사용하여 해시 함수를 슬롯 번호(또는 체인 높이)에 따라 다르게 설정함으로써 이러한 효과를 완화할 수 있습니다. 블록 높이가 증가함에 따라 해시 함수를 하나씩 추가/제거하여 이러한 변경을 점진적으로 적용할 수도 있습니다.
