Quote
The data being sent isn't a set! The order is needed
Ah, of course, I thought I was missing something! Thanks
Topic: compact block relay: why not use Golomb Coded sets for encoding of shortids? (Read 99 times)
January 07, 2021, 12:51:14 PM
Ah, of course, I thought I was missing something! Thanks
January 07, 2021, 09:29:16 AM
In bip 152 compact block relay is described, which consist of a list of 6-byte shortids: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki
In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.
In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.
The data being sent isn't a set! The order is needed. The order could be guessed and a correction to the guess sent, but thats fairly complex.
GCS's savings come mostly from not encoding the permutation of elements. (Some savings comes from non-duplication, but when the 2^keybits is large compared to the number of entries, non-duplication saves very little.)
There are ways to make compact blocks smaller, much smaller in fact-- e.g. I had a prototype implementation that used minisketch which made typical compact blocks about 800 bytes. But there seems to be littler reason to bother further reducing the size right now.
(This also required the above mentioned guess and correct ordering-- in my case I didn't implement correction and only supported it on blocks where the guess was 100% correct: ones where the miner didn't use prioritization, which is most of them)
Probably more important would be techniques from fibre that let blocks propagate unconditionally without round trips at all even when some txn are missing or some packets are lost.
January 07, 2021, 09:04:29 AM
In bip 152 compact block relay is described, which consist of a list of 6-byte shortids: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki
In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.
In bip 158 Golomb-Coded Sets are described, which sounds to me like the ideal data structure for these IDs. I wonder if it would be beneficial to encode & transmit a golomb-coded sets for the shortids instead of the fixed 6-bytes? It should reduce the size of the transmitted data a bit, at the cost of a bit more processing power.
Jump to: