Хватит качать и хранить нули

    Скачиваемый файл заполнен нулями


    "Нуль-блоками" я называю блоки (части файла), заполненные нулевыми байтами. Можно заранее посчитать их хеши и не запрашивать эти блоки у источников, а сразу помечать их уже загруженными.


    Нуль-блоки не надо хранить на диске. Благодаря sparse флагу, операционная система просто помечает этот участок файла как заполненный нулями и не хранит эти нули на диске.


    Свойства файла заполненного нулями

    Файл размером 16MB занимает на диске 4KB


    Также, показывая что участки скачиваемого файла заполнены нулями, можно мотивировать пользователя отказаться от скачивания и распространения битого файла. В моей версии Shareaza эти участки помечаются красной полосой сверху на полосе прогресса загрузки файла.


    Откуда берутся нуль-блоки в файле


    1. Раздающий не дождался полного скачивания и проверки файла и выложил неполный(partial) файл.
    2. Результат повреждения сектора диска раздающего.

    Это те варианты, которые пришли в голову.


    Почему эти файлы продолжают распространяться


    1. Видео/аудио файл может иметь нуль-блок в середине и спокойно воспроизводится, просто перескакивая то место, где попался нуль-блок. Тем самым он может казаться целым.
    2. Образ диска также может иметь нуль-блоки в разных местах и это проявит себя только при попытке чтения файлов из этих блоков.

    Как это работает


    1. Перед загрузкой файла p2p клиент получает от источника список хешей блоков.
    2. Каждый хеш из списка сравнивается с заранее вычисленными хешами нуль-блоков.
    3. Те блоки, у которых хеш совпал с хешем нуль-блока, помечаются уже загруженными. Пользователю дополнительно отображается, что в этом месте одни нули.

    Инструменты для вычисления нуль-блоков


    1. RHash — он будет непосредственно считать хеши.
    2. Lua — будет загружать в RHash необходимое количество нулей и выводить результаты.
    3. Общие функции скрипта:


      local lua = "lua5.1"                  -- интерпретатор
      local script_name = "zero-block-hash" -- название скрипта (имя файла без расширения)
      
      -- декодирует строку из hex в бинарное представление
      -- https://stackoverflow.com/a/9140231
      function string.fromhex(str)
          return (str:gsub('..', function (cc)
              return string.char(tonumber(cc, 16))
          end))
      end
      
      -- выводит в io.stdout заданное количество нулей
      function std_write(size)
          index = index or 0;
      
          local buffer_size = 1024*1024*16;
      
          if ( size <= buffer_size ) then
              io.stdout:write( ('\0'):rep( size  ) );
          else
              local zero_buffer = ('\0'):rep( buffer_size );
      
              local count = math.floor( size / #zero_buffer );
              local tail = math.fmod( size, #zero_buffer );
      
              for i = 1, count do
                  io.stdout:write( zero_buffer );
              end
      
              if ( tail > 0 ) then
                  io.stdout:write( zero_buffer:sub( 1, tail ) );
              end
          end
      end


    Не качаем нули из сети EDonkey2000


    md4(block_data)

    ED2K хеш самый простой. У него фиксированный размер блока 9728000 байт. Блоки обрабатываются функцией md4. Понадобится вычислить только одно значение хеша.


    Считаем md4 хеш:


    --ED2K zero block
    local md4_cmd = lua..' -l"'..script_name..'" -e"std_write(9728000);"|rhash -p"%x{md4}" -';
    
    function gen_md4_hash()
        -- запускаем функцию std_write которая передаёт в RHash необходимое количество нулевых байт.
        local md4 = io.popen(md4_cmd, "rb");
    
        -- получаем результат вычислений
        local hash = md4:read("*a"):upper(); 
    
        -- выводим результат
        print("")
        print("// md4_hash")
        print("// Hash: "..hash, "Size: 9728000");
        md4:close();
    end

    Запускаем:


    lua5.1 -l "zero-block-hash" -e"gen_md4_hash()"

    Результат:


    // md4_hash
    // Hash: D7DEF262A127CD79096A108E7A9FC138       Size: 9728000

    MD4 от 9728000 нулевых байт: D7DEF262A127CD79096A108E7A9FC138


    Детектор ED2K нуль-блока Shareaza:


    BOOL CED2K::IsZeroBlock(uint32 nBlock) const
    {
        // Hash: D7DEF262A127CD79096A108E7A9FC138      Size: 9728000
        static const uint32 ZeroHash[ 4 ] = { 0x62F2DED7, 0x79CD27A1, 0x8E106A09, 0x38C19F7A };
        return memcmp( &ZeroHash, m_pList[ nBlock ].data, sizeof( ZeroHash ) ) == 0;
    }

    GitHub: ED2K.cpp#L334


    Не качаем нули из сети BitTorrent


    С BitTorrent посложнее. Минимальный размер блока у BitTorrent это 16384 байт. Далее размер блока удваивается.


    Хеш блока это результат работы функции SHA1 над данными блока:


    sha1(block_data)

    Считаем sha1 хеши:


    --Bittorrent zero block
    local sha1_cmd = lua..' -l"'..script_name..'" -e"std_write(%s);"|rhash -p"%%x{sha1}" -';
    
    function gen_sha1_hashes(hash_count)
        local size = 16384 -- минимальный размер блока
        local sha1 = {};
        hash_count = hash_count or 13; -- по умолчанию считаем 13 хешей
    
        -- параллельные вычисления
        -- запускаем счёт хешей передавая размер блока в std_write
        for i = 1, hash_count do
            sha1[i] = io.popen(sha1_cmd:format(size), "rb");
            size = size * 2;
        end
    
        size = 16384
        -- получаем результаты
        print("")
        print("// sha1_hashes")
        for i = 1, #sha1 do
            local hash = sha1[i]:read("*a"):upper();
            sha1[i]:close();
            print( "// Hash: " .. hash .. "\tSize: " .. size );
            size = size * 2;
        end
    end

    Запускаем:


    lua5.1 -l "zero-block-hash" -e"gen_sha1_hashes()"

    Мне терпения хватило дождаться вычисления 22 нуль-блоков. Но и этого с избытком. С трудом представляю себе торрент с блоком в 34GB:


    // sha1_hashes
    // Hash: 897256B6709E1A4DA9DABA92B6BDE39CCFCCD8C1       Size: 16384
    // Hash: 5188431849B4613152FD7BDBA6A3FF0A4FD6424B       Size: 32768
    // Hash: 1ADC95BEBE9EEA8C112D40CD04AB7A8D75C4F961       Size: 65536
    // Hash: 67DFD19F3EB3649D6F3F6631E44D0BD36B8D8D19       Size: 131072
    // Hash: 2E000FA7E85759C7F4C254D4D9C33EF481E459A7       Size: 262144
    // Hash: 6A521E1D2A632C26E53B83D2CC4B0EDECFC1E68C       Size: 524288
    // Hash: 3B71F43FF30F4B15B5CD85DD9E95EBC7E84EB5A3       Size: 1048576
    // Hash: 7D76D48D64D7AC5411D714A4BB83F37E3E5B8DF6       Size: 2097152
    // Hash: 2BCCBD2F38F15C13EB7D5A89FD9D85F595E23BC3       Size: 4194304
    // Hash: 5FDE1CCE603E6566D20DA811C9C8BCCCB044D4AE       Size: 8388608
    // Hash: 3B4417FC421CEE30A9AD0FD9319220A8DAE32DA2       Size: 16777216
    // Hash: 57B587E1BF2D09335BDAC6DB18902D43DFE76449       Size: 33554432
    // Hash: 44FAC4BEDDE4DF04B9572AC665D3AC2C5CD00C7D       Size: 67108864
    // Hash: BA713B819C1202DCB0D178DF9D2B3222BA1BBA44       Size: 134217728
    // Hash: 7B91DBDC56C5781EDF6C8847B4AA6965566C5C75       Size: 268435456
    // Hash: 5B088492C9F4778F409B7AE61477DEC124C99033       Size: 536870912
    // Hash: 2A492F15396A6768BCBCA016993F4B4C8B0B5307       Size: 1073741824
    // Hash: 91D50642DD930E9542C39D36F0516D45F4E1AF0D       Size: 2147483648
    // Hash: 1BF99EE9F374E58E201E4DDA4F474E570EB77229       Size: 4294967296
    // Hash: BCC8C0CA9E402EEE924A6046966D18B1F66EB577       Size: 8589934592
    // Hash: DC44DD38511BD6D1233701D63C15B87D0BD9F3A5       Size: 17179869184
    // Hash: 7FFB233B3B2806328171FB8B5C209F48DC095B72       Size: 34359738368

    Детектор BitTorrent нуль-блока в Shareaza
    BOOL CBTInfo::IsZeroBlock(uint32 nBlock) const
    {
        static const uint32 ZeroHash[22][5] = {
            // Hash: 897256B6709E1A4DA9DABA92B6BDE39CCFCCD8C1       Size: 16384
            { 0xB6567289, 0x4D1A9E70, 0x92BADAA9, 0x9CE3BDB6, 0xC1D8CCCF },
            // Hash: 5188431849B4613152FD7BDBA6A3FF0A4FD6424B       Size: 32768
            { 0x18438851, 0x3161B449, 0xDB7BFD52, 0x0AFFA3A6, 0x4B42D64F },
            // Hash: 1ADC95BEBE9EEA8C112D40CD04AB7A8D75C4F961       Size: 65536
            { 0xBE95DC1A, 0x8CEA9EBE, 0xCD402D11, 0x8D7AAB04, 0x61F9C475 },
            // Hash: 67DFD19F3EB3649D6F3F6631E44D0BD36B8D8D19       Size: 131072
            { 0x9FD1DF67, 0x9D64B33E, 0x31663F6F, 0xD30B4DE4, 0x198D8D6B },
            // Hash: 2E000FA7E85759C7F4C254D4D9C33EF481E459A7       Size: 262144
            { 0xA70F002E, 0xC75957E8, 0xD454C2F4, 0xF43EC3D9, 0xA759E481 },
            // Hash: 6A521E1D2A632C26E53B83D2CC4B0EDECFC1E68C       Size: 524288
            { 0x1D1E526A, 0x262C632A, 0xD2833BE5, 0xDE0E4BCC, 0x8CE6C1CF },
            // Hash: 3B71F43FF30F4B15B5CD85DD9E95EBC7E84EB5A3       Size: 1048576
            { 0x3FF4713B, 0x154B0FF3, 0xDD85CDB5, 0xC7EB959E, 0xA3B54EE8 },
            // Hash: 7D76D48D64D7AC5411D714A4BB83F37E3E5B8DF6       Size: 2097152
            { 0x8DD4767D, 0x54ACD764, 0xA414D711, 0x7EF383BB, 0xF68D5B3E },
            // Hash: 2BCCBD2F38F15C13EB7D5A89FD9D85F595E23BC3       Size: 4194304
            { 0x2FBDCC2B, 0x135CF138, 0x895A7DEB, 0xF5859DFD, 0xC33BE295 },
            // Hash: 5FDE1CCE603E6566D20DA811C9C8BCCCB044D4AE       Size: 8388608
            { 0xCE1CDE5F, 0x66653E60, 0x11A80DD2, 0xCCBCC8C9, 0xAED444B0 },
            // Hash: 3B4417FC421CEE30A9AD0FD9319220A8DAE32DA2       Size: 16777216
            { 0xFC17443B, 0x30EE1C42, 0xD90FADA9, 0xA8209231, 0xA22DE3DA },
            // Hash: 57B587E1BF2D09335BDAC6DB18902D43DFE76449       Size: 33554432
            { 0xE187B557, 0x33092DBF, 0xDBC6DA5B, 0x432D9018, 0x4964E7DF },
            // Hash: 44FAC4BEDDE4DF04B9572AC665D3AC2C5CD00C7D       Size: 67108864
            { 0xBEC4FA44, 0x04DFE4DD, 0xC62A57B9, 0x2CACD365, 0x7D0CD05C },
            // Hash: BA713B819C1202DCB0D178DF9D2B3222BA1BBA44       Size: 134217728
            { 0x813B71BA, 0xDC02129C, 0xDF78D1B0, 0x22322B9D, 0x44BA1BBA },
            // Hash: 7B91DBDC56C5781EDF6C8847B4AA6965566C5C75       Size: 268435456
            { 0xDCDB917B, 0x1E78C556, 0x47886CDF, 0x6569AAB4, 0x755C6C56 },
            // Hash: 5B088492C9F4778F409B7AE61477DEC124C99033       Size: 536870912
            { 0x9284085B, 0x8F77F4C9, 0xE67A9B40, 0xC1DE7714, 0x3390C924 },
            // Hash: 2A492F15396A6768BCBCA016993F4B4C8B0B5307       Size: 1073741824
            { 0x152F492A, 0x68676A39, 0x16A0BCBC, 0x4C4B3F99, 0x07530B8B },
            // Hash: 91D50642DD930E9542C39D36F0516D45F4E1AF0D       Size: 2147483648
            { 0x4206D591, 0x950E93DD, 0x369DC342, 0x456D51F0, 0x0DAFE1F4 },
            // Hash: 1BF99EE9F374E58E201E4DDA4F474E570EB77229       Size: 4294967296
            { 0xE99EF91B, 0x8EE574F3, 0xDA4D1E20, 0x574E474F, 0x2972B70E },
            // Hash: BCC8C0CA9E402EEE924A6046966D18B1F66EB577       Size: 8589934592
            { 0xCAC0C8BC, 0xEE2E409E, 0x46604A92, 0xB1186D96, 0x77B56EF6 },
            // Hash: DC44DD38511BD6D1233701D63C15B87D0BD9F3A5       Size: 17179869184
            { 0x38DD44DC, 0xD1D61B51, 0xD6013723, 0x7DB8153C, 0xA5F3D90B },
            // Hash: 7FFB233B3B2806328171FB8B5C209F48DC095B72       Size: 34359738368
            { 0x3B23FB7F, 0x3206283B, 0x8BFB7181, 0x489F205C, 0x725B09DC }
        };
    
        int i = 0;
        for(; m_nBlockSize > ( (uint64) 16384 << i ); i++)
            if ( i > 21 )
                return FALSE;
    
        return memcmp( &m_pBlockBTH[ nBlock ], ZeroHash[ i ], sizeof( ZeroHash[ i ] ) ) == 0;
    }

    GitHub: BTInfo.cpp#L1611


    Не качаем нули из сетей DirectConnect, Gnutella и Gnutella2


    Эти три сети используют Tree Tiger Hash (TTH). Исходя из названия, это дерево хешей, а для вычисления используется функция Tiger. Я такие типы хешей называю "деревянные". TTH, на мой взгляд, самое простое дерево и, благодаря его свойствам, мы очень быстро можем вычислить хеш для разных размеров блока.


    Минимальный размер блока у TTH это 1024 байта. Далее размер блока удваивается на каждом уровне.


    Вычисляется он так:


    Tiger(0x00 + block_data)

    0x00 — байт префикс Leaf блока
    block_data — данные блока(в нашем случае это 1024 нулевых байта)
    + — конкатенация
    Tiger — хеш функция


    Далее, для того, чтобы вычислить нуль-блоки большего размера, мы используем хеш от нуль-блока меньшего размера.


    Tiger(0x01 + hash + hash)

    0x01 — байт префикс для пары хешей
    hash — хеш нуль-блока, который мы получили на предыдущем уровне.
    Tiger — хеш функция


    Пишем функции для вычисления:


    --Tiger Tree Hash Leaf block
    local leaf_hash_cmd = lua..' -l"'..script_name..'" -e"std_write_leaf_hash()"';
    
    --Tiger Tree Hash Internal block
    local internal_hash_cmd = lua..' -l"'..script_name..'" -e"std_write_internal_hash(\'%s\')"';
    
    -- передаёт в rhash нуль-блок с префиксом '\0'  
    function std_write_leaf_hash()
        local tiger = io.popen('rhash -p"%x{tiger}" -', "wb") 
        tiger:write('\0'..('\0'):rep(1024))
        tiger:close()
    end
    
    -- передаёт в rhash пару одинаковых хешей с префиксом '\1'
    function std_write_internal_hash(hash)
        local tiger = io.popen('rhash -p"%x{tiger}" -', "wb");
        hash = hash:fromhex();
        tiger:write('\1'..hash..hash)
        tiger:close()
    end
    
    -- хеш от нуль-блока
    function tth_leaf()
        local rhash = io.popen(leaf_hash_cmd, "rb");
        local hash = rhash:read("*a");
        rhash:close();
        return hash;
    end
    
    -- хеш от пары одинаковых хешей
    function tth_root(hash_hex)
        local rhash = io.popen(internal_hash_cmd:format(hash_hex), "rb");
        local hash = rhash:read("*a");
        rhash:close();
        return hash;
    end
    
    -- вычисляем заданное количество хешей
    function gen_tth_hashes(hash_count)
        -- получаем хеш от нуль-блока
        local hash_hex = tth_leaf():upper();
        hash_count = hash_count or 37;
        hash_count = hash_count - 1;
        print("")
        print("// tth_hashes")
        for i = 0, hash_count do
            print("// Hash: "..hash_hex, " Size: "..math.floor(1024*2^i));
             -- получаем хеш от нуль-блока вдвое большего размера
            hash_hex = tth_root(hash_hex):upper();
        end
    end

    Запускаем:


    lua5.1 -l "zero-block-hash" -e"gen_tth_hashes()"

    В результате я очень быстро получил 37 нуль-блоков. Дальше были проблемы с отображением размера блока у скрипта. Но и этих значений с избытком. Последний блок размером в 70TB.


    // tth_hashes
    // Hash: 13143C45D95485EACD9C47D72630EF0139436CB77DF2632B        Size: 1024
    // Hash: 855DCE7FE3E963F50295A673120E6259165CED9F086DB031        Size: 2048
    // Hash: 38FB763B44ECA3B13F40182C75694360AC8DA0865DDB29D6        Size: 4096
    // Hash: 721BEF53CBBDA47BE44BD26C43EC048F136D371E918200CF        Size: 8192
    // Hash: AFDDF505C1E1D5AF8FAE007BBE4E64578F34D912345E23D8        Size: 16384
    // Hash: 53CC478ED14FF7FB671F94ECE0FD7C8C5DCB2FE611ACAC6B        Size: 32768
    // Hash: 098B212D6EE0398D319D4F1807E87235A0B8665BA46EF77F        Size: 65536
    // Hash: 69940A3C20C43576D258BD210339565711D696E94A3511EB        Size: 131072
    // Hash: FA4317C074C2D7CD9BBFD7F4C8BD3F9F79F330F0C27B61B8        Size: 262144
    // Hash: AF8E46E049A800C2339E863AF390C5CFF02BCC39025D44AA        Size: 524288
    // Hash: 650022207EA4EB454E24D3279539F3CCD92F034E2F83CCB7        Size: 1048576
    // Hash: 0BED4DF002309E7D33D52ED0D5C3C24B1ECAA330CBAFB723        Size: 2097152
    // Hash: 2FFF449E538E158CD346C5BF7778F2FF67383707955C72C1        Size: 4194304
    // Hash: F2D3852A12C25C0C1EE124C07144C6CFA3CD0E72DB9364F8        Size: 8388608
    // Hash: 8E6FD02F7F9A0D5233E9287C6D139D44DE76BB80BCBD8BEC        Size: 16777216
    // Hash: F98C3CB14C4B501DCEF346D6FB92E56AC3F96102B17468F4        Size: 33554432
    // Hash: 1830D2019F1A54C7A8A3947E36D34A4E676523FF0735E0FC        Size: 67108864
    // Hash: 3D002613BA2F88DA7D7E1AB165677FC939B5EC6FFD5D2E73        Size: 134217728
    // Hash: BC0466EE7A0C30E31EFD803598BE8F69400B96AE3126AF70        Size: 268435456
    // Hash: 31D3A13D9F1BD0D2E16FF2BF6749F830D81693D63E4C1903        Size: 536870912
    // Hash: 6EF9A41AEC7C0C0B821D3A845994E6F18E5268E37BC982C1        Size: 1073741824
    // Hash: 13132A77BAB0B8A0130FC2B5BF6C36701C622A36AFFBD175        Size: 2147483648
    // Hash: E684CA0E3D759457F3F2B4183A0889B25C49F70AB5B5AD8E        Size: 4294967296
    // Hash: 8C4AEAB1D5A2E3ABBD19848EBC9813121A83D196320EFE54        Size: 8589934592
    // Hash: 2CB4627DB09C230212258BAD4120AA0A1C4A185BD2CC4C57        Size: 17179869184
    // Hash: B58DE81DC064E964720A0C181AE6EF415F865BAA18E9F019        Size: 34359738368
    // Hash: EC0B596EFA9EDBEFE275539914F30757E2E3EB82C30B6FB8        Size: 68719476736
    // Hash: BA0078DAD436099159ADA9CFA1457806EB581730364084E0        Size: 137438953472
    // Hash: D96DA2416DBF7DAC663872838F8F4E7D8E7C4D2D2A2051AB        Size: 274877906944
    // Hash: 74816B22B67E4E6995FECAEB84302D01E489BCD76845444B        Size: 549755813888
    // Hash: 307DB672C03531EB0E9B19FC2ED134ACCEFFB4E04D8EB62D        Size: 1099511627776
    // Hash: 43CD6009D7931ECC1FFC484D8156A92EC673DEF3D6AE7CF9        Size: 2199023255552
    // Hash: 84814323435A450426EECC6700349387D61BD5027F6E7085        Size: 4398046511104
    // Hash: 05275B3D69A996B1E8ABDA6EACE8605D5BB7DD8964AC4C79        Size: 8796093022208
    // Hash: 434934E2D0EFDEE9864982221FB8A0A872D842B4DA6C59E7        Size: 17592186044416
    // Hash: 435396F0F684A6B3E5B5940A79800EE384915CCAD7C52385        Size: 35184372088832
    // Hash: 7F377469FB6883D13331667F52CF23194846311094A363C4        Size: 70368744177664

    Детектор TigerTree нуль-блока в Shareaza
    BOOL CTigerTree::IsZeroBlock(uint32 nBlock) const
    {
        static const uint64 ZeroHash[37][3] =
        {
            // Hash: 13143C45D95485EACD9C47D72630EF0139436CB77DF2632B        Size: 1024
            { 0xEA8554D9453C1413, 0x01EF3026D7479CCD, 0x2B63F27DB76C4339 },
            // Hash: 855DCE7FE3E963F50295A673120E6259165CED9F086DB031        Size: 2048
            { 0xF563E9E37FCE5D85, 0x59620E1273A69502, 0x31B06D089FED5C16 },
            // Hash: 38FB763B44ECA3B13F40182C75694360AC8DA0865DDB29D6        Size: 4096
            { 0xB1A3EC443B76FB38, 0x604369752C18403F, 0xD629DB5D86A08DAC },
            // Hash: 721BEF53CBBDA47BE44BD26C43EC048F136D371E918200CF        Size: 8192
            { 0x7BA4BDCB53EF1B72, 0x8F04EC436CD24BE4, 0xCF0082911E376D13 },
            // Hash: AFDDF505C1E1D5AF8FAE007BBE4E64578F34D912345E23D8        Size: 16384
            { 0xAFD5E1C105F5DDAF, 0x57644EBE7B00AE8F, 0xD8235E3412D9348F },
            // Hash: 53CC478ED14FF7FB671F94ECE0FD7C8C5DCB2FE611ACAC6B        Size: 32768
            { 0xFBF74FD18E47CC53, 0x8C7CFDE0EC941F67, 0x6BACAC11E62FCB5D },
            // Hash: 098B212D6EE0398D319D4F1807E87235A0B8665BA46EF77F        Size: 65536
            { 0x8D39E06E2D218B09, 0x3572E807184F9D31, 0x7FF76EA45B66B8A0 },
            // Hash: 69940A3C20C43576D258BD210339565711D696E94A3511EB        Size: 131072
            { 0x7635C4203C0A9469, 0x5756390321BD58D2, 0xEB11354AE996D611 },
            // Hash: FA4317C074C2D7CD9BBFD7F4C8BD3F9F79F330F0C27B61B8        Size: 262144
            { 0xCDD7C274C01743FA, 0x9F3FBDC8F4D7BF9B, 0xB8617BC2F030F379 },
            // Hash: AF8E46E049A800C2339E863AF390C5CFF02BCC39025D44AA        Size: 524288
            { 0xC200A849E0468EAF, 0xCFC590F33A869E33, 0xAA445D0239CC2BF0 },
            // Hash: 650022207EA4EB454E24D3279539F3CCD92F034E2F83CCB7        Size: 1048576
            { 0x45EBA47E20220065, 0xCCF3399527D3244E, 0xB7CC832F4E032FD9 },
            // Hash: 0BED4DF002309E7D33D52ED0D5C3C24B1ECAA330CBAFB723        Size: 2097152
            { 0x7D9E3002F04DED0B, 0x4BC2C3D5D02ED533, 0x23B7AFCB30A3CA1E },
            // Hash: 2FFF449E538E158CD346C5BF7778F2FF67383707955C72C1        Size: 4194304
            { 0x8C158E539E44FF2F, 0xFFF27877BFC546D3, 0xC1725C9507373867 },
            // Hash: F2D3852A12C25C0C1EE124C07144C6CFA3CD0E72DB9364F8        Size: 8388608
            { 0x0C5CC2122A85D3F2, 0xCFC64471C024E11E, 0xF86493DB720ECDA3 },
            // Hash: 8E6FD02F7F9A0D5233E9287C6D139D44DE76BB80BCBD8BEC        Size: 16777216
            { 0x520D9A7F2FD06F8E, 0x449D136D7C28E933, 0xEC8BBDBC80BB76DE },
            // Hash: F98C3CB14C4B501DCEF346D6FB92E56AC3F96102B17468F4        Size: 33554432
            { 0x1D504B4CB13C8CF9, 0x6AE592FBD646F3CE, 0xF46874B10261F9C3 },
            // Hash: 1830D2019F1A54C7A8A3947E36D34A4E676523FF0735E0FC        Size: 67108864
            { 0xC7541A9F01D23018, 0x4E4AD3367E94A3A8, 0xFCE03507FF236567 },
            // Hash: 3D002613BA2F88DA7D7E1AB165677FC939B5EC6FFD5D2E73        Size: 134217728
            { 0xDA882FBA1326003D, 0xC97F6765B11A7E7D, 0x732E5DFD6FECB539 },
            // Hash: BC0466EE7A0C30E31EFD803598BE8F69400B96AE3126AF70        Size: 268435456
            { 0xE3300C7AEE6604BC, 0x698FBE983580FD1E, 0x70AF2631AE960B40 },
            // Hash: 31D3A13D9F1BD0D2E16FF2BF6749F830D81693D63E4C1903        Size: 536870912
            { 0xD2D01B9F3DA1D331, 0x30F84967BFF26FE1, 0x03194C3ED69316D8 },
            // Hash: 6EF9A41AEC7C0C0B821D3A845994E6F18E5268E37BC982C1        Size: 1073741824
            { 0x0B0C7CEC1AA4F96E, 0xF1E69459843A1D82, 0xC182C97BE368528E },
            // Hash: 13132A77BAB0B8A0130FC2B5BF6C36701C622A36AFFBD175        Size: 2147483648
            { 0xA0B8B0BA772A1313, 0x70366CBFB5C20F13, 0x75D1FBAF362A621C },
            // Hash: E684CA0E3D759457F3F2B4183A0889B25C49F70AB5B5AD8E        Size: 4294967296
            { 0x5794753D0ECA84E6, 0xB289083A18B4F2F3, 0x8EADB5B50AF7495C },
            // Hash: 8C4AEAB1D5A2E3ABBD19848EBC9813121A83D196320EFE54        Size: 8589934592
            { 0xABE3A2D5B1EA4A8C, 0x121398BC8E8419BD, 0x54FE0E3296D1831A },
            // Hash: 2CB4627DB09C230212258BAD4120AA0A1C4A185BD2CC4C57        Size: 17179869184
            { 0x02239CB07D62B42C, 0x0AAA2041AD8B2512, 0x574CCCD25B184A1C },
            // Hash: B58DE81DC064E964720A0C181AE6EF415F865BAA18E9F019        Size: 34359738368
            { 0x64E964C01DE88DB5, 0x41EFE61A180C0A72, 0x19F0E918AA5B865F },
            // Hash: EC0B596EFA9EDBEFE275539914F30757E2E3EB82C30B6FB8        Size: 68719476736
            { 0xEFDB9EFA6E590BEC, 0x5707F314995375E2, 0xB86F0BC382EBE3E2 },
            // Hash: BA0078DAD436099159ADA9CFA1457806EB581730364084E0        Size: 137438953472
            { 0x910936D4DA7800BA, 0x067845A1CFA9AD59, 0xE0844036301758EB },
            // Hash: D96DA2416DBF7DAC663872838F8F4E7D8E7C4D2D2A2051AB        Size: 274877906944
            { 0xAC7DBF6D41A26DD9, 0x7D4E8F8F83723866, 0xAB51202A2D4D7C8E },
            // Hash: 74816B22B67E4E6995FECAEB84302D01E489BCD76845444B        Size: 549755813888
            { 0x694E7EB6226B8174, 0x012D3084EBCAFE95, 0x4B444568D7BC89E4 },
            // Hash: 307DB672C03531EB0E9B19FC2ED134ACCEFFB4E04D8EB62D        Size: 1099511627776
            { 0xEB3135C072B67D30, 0xAC34D12EFC199B0E, 0x2DB68E4DE0B4FFCE },
            // Hash: 43CD6009D7931ECC1FFC484D8156A92EC673DEF3D6AE7CF9        Size: 2199023255552
            { 0xCC1E93D70960CD43, 0x2EA956814D48FC1F, 0xF97CAED6F3DE73C6 },
            // Hash: 84814323435A450426EECC6700349387D61BD5027F6E7085        Size: 4398046511104
            { 0x04455A4323438184, 0x8793340067CCEE26, 0x85706E7F02D51BD6 },
            // Hash: 05275B3D69A996B1E8ABDA6EACE8605D5BB7DD8964AC4C79        Size: 8796093022208
            { 0xB196A9693D5B2705, 0x5D60E8AC6EDAABE8, 0x794CAC6489DDB75B },
            // Hash: 434934E2D0EFDEE9864982221FB8A0A872D842B4DA6C59E7        Size: 17592186044416
            { 0xE9DEEFD0E2344943, 0xA8A0B81F22824986, 0xE7596CDAB442D872 },
            // Hash: 435396F0F684A6B3E5B5940A79800EE384915CCAD7C52385        Size: 35184372088832
            { 0xB3A684F6F0965343, 0xE30E80790A94B5E5, 0x8523C5D7CA5C9184 },
            // Hash: 7F377469FB6883D13331667F52CF23194846311094A363C4        Size: 70368744177664
            { 0xD18368FB6974377F, 0x1923CF527F663133, 0xC463A39410314648 }
        };
    
        CSectionLock oLock( &m_pSection );
    
        if ( nBlock >= m_nBaseUsed ) return FALSE;
        if ( m_nActualHeight < m_nHeight ) return FALSE;
    
        uint32 nBlockHeight = m_nActualHeight - m_nHeight;
    
        if ( nBlockHeight > 36 ) return FALSE;
    
        CTigerNode* pBase = m_pNode + m_nNodeCount - m_nNodeBase + nBlock;
        return memcmp( ZeroHash[ nBlockHeight ], pBase->value, sizeof( pBase->value ) ) == 0;
    }

    GitHub: TigerTree.cpp#L1298


    Хвосты


    Хвост это неполный блок в конце файла. Хвост у файла один и мы можем для него индивидуально посчитать хеш, если бы он был заполнен нулями. И в случае, если хеш хвоста и вычисленный совпадают, помечаем его также загруженным.


    Ещё не реализовал данную функцию.


    Заключение


    Надеюсь данную инструкцию возьмут на вооружение и добавят этот функционал в свои peer-to-peer клиенты и в сети будет циркулировать больше полезных данных.


    Ссылки


    Скрипт: zero-block-hash.lua
    Торрент c файлом, заполненным нулями: testfile.torrent

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 90

      +9
      На самом деле, нельзя слепо полагаться на одни только хэши: ни одна функция хэширования не может обеспечить отсутствия коллизий, соответственно, существуют непостижимое множество вариантов ненулевого заполнения блоков, хэши от которых будут совпадать с хэшами нулевых блоков того же размера
        –2
        Да есть такая вероятность. Но ей думаю можно спокойно пренибечь.
          +7
          Известные гипотетические обезьянки, набирающие случайный текст существенно (на многие-многие порядки) более вероятно наберут текст, хэш от которого совпадёт с хэшем от текста «Войны и Мира», чем сам текст «Войны и Мира». Так что нет, не соглашусь, по крайней мере, не со «спокойно»
            0
            Если не спокойно то можно в конце загрузки запросить случайный небольшой участок нуль блока. И если там вдруг окажутся не нули то скачать его полностью.
              0
              А если идёт подрят несколько нульблоков то там уж точно должны быть нули и можно не перепроверять.
              0
              И тем не менее вероятность коллизии остается пренебрежимо малой, а именно 1/2^(количество бит хэша).
                0
                Тогда добавьте вероятность, что вам могут подсунуть другой файл с тем же хэшем, порядок ваших опасений примерно статистически на таком же уровне
                  0
                  Нет. В данном случае один хэш на файл. У вас же 1 хэш на блок.
                  Сколько в среднем блоков в файле?
                  Почти во столько раз будет больше вероятность.
                    0
                    Правильно — в разы…
                    Но вероятность что разные файлы будут с одинаковым хэшем — на порядки меньше
                      0
                      В том-то и дело, что не разные, а одинаковые.

                      В случае с BT мы имеем (упрощенно)
                      80 байт представляющих любую последовательность из 16k байт. Одна из них определенно представлена нулями, но сколько еще последовательностей с ней совпадают по хешу?

                      В случае с конкретным файлом и конкретной длинной хешируемых данных, то чем больше файл и меньше рамер единицы хешируемых, то вероятность совпадения уменьшается. Но и тогда она никогда не будет равна нулю, даже если размер хешируемых будет равен исходным, кроме изначально уникальных ситуаций.
                  –2
                  В вашей Параллельной Вселенной и функции хэширования идеальные и злоумышленников не существует, а в Нашей это не так
                    +6
                    Каким образом мошенники могут использовать нуль-блоки? То есть он такой: «Найду ка я коллизию с хешем нуль-блока и выложу торрент. И у меня никто эти блоки не будет качать. Они никогда не узнают содержимое псевдонуль-блоков которое я вычислил.»
                      0
                      В комментарии, на который вы ответили я говорил в общем о функциях хэширования
                      • UFO just landed and posted this here
                        +2
                        Даже если опустить все детали указанные выше, объясните мне пожалуйста, как вы создадите вредоносный код, который будет при этом иметь коллизию с нуль-блоком.
                          –2
                          Вы слишком цепляетесь за контекст статьи и беседы: я говорил о функциях хэширования в целом
                          0
                          Может в вашей Параллельной Вселенной кто-нибудь уже научился подделывать хотя бы MD4 (про MD5 и SHA1 вообще молчу)?

                          Расскажите — интересно же! А в нашей вселенной эта задача настолько сложна, что её до сих пор не умеют решать…

                          P.S. Только перед тем, как вы начнёте давать нерелевантные ссылки рекомендую на досуге почитать пару статей в Wikipedia, понять, чем атака нахождения прообраза отличается от коллизионной атака — тогда, может быть, поймёте почему в данном конкретном случае SHA1 достаточно (а можно было бы MD4 использовать, да).
                            –1
                            Вы меня с кем-то путаете, я лишь говорил о том, что опрометчиво оценивать вероятность коллизии на основании лишь двух заведомо неверных предположениях:
                            • Функция хэширования идеальна
                            • Хэшируемые данные случайны
                              0
                              Неидеальность функции хэширования не значима (пока не доказано обратное), а случайность хэшируемых данных здесь вообще не при чем.
                                +2
                                Вы, кажется, путаете статистические характеристики хэшируемых данных и их происхождение, я говорил о втором: данные в скачиваемом файле не являются случайными, блоки, заполненные нулями — тем более. Случайность данных — ключевая характеристика для рассуждений о вероятности коллизий: для утверждений о вероятности, по крайней мере один из двух наборов данных, вероятность совпадения хэшей которых оценивается, должен быть выбран произвольно из множества вариантов, мощность которого сравнима с мощностью области значений функции хэширования
                                  +2
                                  Это вы путаете распределение входных данных (неслучайное) и распределение хэшей (близкое к случайному равномерному независимо от входных данных). Поэтому если вам дан хэш от блока нулей, то ваш шанс найти набор данных дающий такой же хэш является 1/2^количество бит, как вам уже показывали сверху в статье с вики (опять же, пока не найден более эффективный алгоритм атаки, что верно для того же SHA).
                                    –1
                                    Поэтому если вам дан хэш от блока нулей, то ваш шанс найти набор данных дающий такой же хэш является 1/2^количество бит
                                    это утверждение верно лишь для идеальной функции хэширования в идеальном (случайном) пространстве множеств данных. Оба условия не соблюдены. Независимо от того, что я путаю выше
                                      +1
                                      Криптостойкость хеш-фунцкии, в том числе, означает что это утверждение верно для любого достаточно большого пространства входных данных.
                                        –1
                                        для любого
                                        приведу пример пространства входных данных, в котором вероятность коллизии будет равна 1:
                                        Возьмём последнюю строку из раздела TTH
                                        по количеству цифр (48) определяем, что выход функции 768-битный (N=768)
                                        Возьмём множество всех возможных значений исходных данных объёмомом M=70368744177664*8 бит (в таблице объём в байтах) с неким фиксированным значением хэша, например, 7FFB233B3B2806328171FB8B5C209F48DC095B72. В нём будет 2^(70368744177664*8-768) элементов с одним и тем же значением функции хэширования.
                                        достаточно большого
                                        достаточно большое, или надо ещё больше?
                                        И это для идеальной функции хэширования, неидеальная увеличивает такое пространство минимум в 2 раза
                                          0
                                          Хорошо, поправка: для любого вычислимого за разумное время достаточно большого множества исходных данных.
                                            0
                                            Сформулируйте своё утверждение полностью, пожалуйста
                                            0
                                            Вы вот вроде все правильно считаете, но не делаете правильный вывод. Да, будет очень много строк с одним значением функции (по опеределению хэш-функции, черт возьми). Но при этом для ваших 768 бит будет 2^768 разных значений, что естественно на миллиард порядков меньше, чем входных данных, и при этом всё равно невычислимо.
                                              0
                                              А вот теперь укажите мне, где же я на что-то подобное претендовал.
                                              В самом первом сообщении я указал на то, что нельзя полагаться только на хэши и я продолжаю на этом настаивать.
                                              Продолжаю указывать, что вы рассчитываете вероятность для идеальных условий, находясь в реальных и игнорируете мои указания на это (вновь и вновь приводя одни и те же аргументы, которые годятся только для идеального мира)
                                              Вычислимо оно или невычислимо, коллизии будут, и это только вопрос времени (нет, существенно меньшего, чем возраст Вселенной, Нашей или Параллельной)
                                              В этом сообщении всё, на что я претендовал в комментариях к данной статье, и не надо мне приписывать того, что я не говорил и чего не подразумевал.
                                              Проекты по последовательной компрометации функций хэширования (они постепенно движутся от более старых к более новым), хоть и затратили неимоверные вычислительные ресурсы (которые, впрочем, как капля в море по сравнению с ресурсами, затраченными на майнинг), продемонстрировали, что коллизии существуют не только в головах таких как я
                                                0
                                                Проекты по последовательной компрометации функций хэширования (они постепенно движутся от более старых к более новым), хоть и затратили неимоверные вычислительные ресурсы (которые, впрочем, как капля в море по сравнению с ресурсами, затраченными на майнинг), продемонстрировали, что коллизии существуют не только в головах таких как я.
                                                А ещё они продемонстрировали, что подход «вы не рефлексируйте, вы распространяйте» — победил окончательно. Коллизии к рассматриваемой задаче неприменимы, а атаки, которые применимы и от которых вы предлагаете защищаться сломают заодно все интернет-банки, биткойны, CDN, и массу других вещей.

                                                Уверяю вас: в мире, где всё это рухнет вам будет меньше всего интересно искать пустые блоки в файлах.
                                                  0
                                                  … а атаки, которые применимы и от которых вы предлагаете защищаться ...
                                                  укажите же мне, где я что-то предлагаю!
                                                  Хватит приписывать мне слова, которых я не говорил!
                                                0
                                                del
                                  0
                                  Так емнип md5 насколько я знаю успешно атакуется менее чем за сутки. Собственно всякие исследования безопасности БД выяснили, что наивный md5 крайне слабо спасает от атак. Вроде даже в Kali Linux что-то по имеется.
                                    +1
                                    Я специально для таких, как вы «я чёта-там помню, а проверять факты — не царское дело» ссылки поставил выше.

                                    Нет нужной атаки на SHA1, MD5! И даже на MD4 нет! Есть некоторые теоретические идеи, которые могли бы их провести… за время, сравнимое со временем существования вселенной.
                                      –1
                                      Словарные атаки, например. Вполне себе результативная вещь. Где-то была даже исследовательская по теме где чуваки ускоряли обработку этого дела какими-то околостатистическими методами. Это НЕ однозначно обратная функция, которую вы видимо называете нужной, но эффективность тем не менее крайне высокая.
                                      Учитывая, что изначальное сообщение было в контесте безопасности странно слышать о том что атаки на хэши нет и исключительно нахождение прообраза есть единстенно верный пруф небезопасности.
                                        +1
                                        Словарным атакам подвержены любые хеш-функции, независимо от их сложности.

                                        И вряд ли словарная атака применима в данном конкретном случае.
                                          0
                                          Учитывая, что изначальное сообщение было в контесте безопасности странно слышать о том что атаки на хэши нет и исключительно нахождение прообраза есть единстенно верный пруф небезопасности.
                                          Нет. Учитывая, что речь шла о безопасности странно видеть тут популярный подход «а давайте надёргаем дерьма со StackOverflow и подмешаем нам в код — авось заработает».

                                          Этот подход и при обычном-то программировании работает плохо, а к безопасности он неприменим совсем — потому что злоумышленник не будет вас уведомлять о том, что он нашёл дыру, а будет просто её использовать.

                                          Когда вы говорите о безопасности вы всегда должны прежде всего описать — что вы собираетесь гарантировать, а чего нет.

                                          Вы этого не сделали — и потому тащите в рот всякую бяку приводите опасности и проблемы, не имеющие отношения к обсуждаемой задаче.
                                  –1
                                  Одна (!) архитектурная ошибка, незамеченная многочисленной армией криптоаналитиков, может похоронить из вашей формулы не просто заметную, а бОльшую часть бит, например, формально функция 768 бит, а по факту 128, а 640 «съели» монстры вашего тщеславия и самоуверенности
                                    0
                                    Точно так же одна ошибка в процедуре митигации может похоронить всю вашу безопасность нафиг.

                                    А вероятность того, что вы её там посадите — гораздо больше, чем вероятность того, что кто-то найдёт практическую атаку на SHA1. Как я уже сказал: требуемой атаки даже на MD4 (который изначально рассматривался как «быстрый, возможно криптографически нестойкий, хеш») не существует.

                                    Покажите такую — будет о чём говорить.

                                    P.S. Логика тут простая: даже если вы можете предполагать, что в вашей бронированной двери из титана и кевлара может быть трещина идея поставить «для надёжности» ещё одну дверь из картона рядом — плоха.
                                      0
                                      Читайте пожалуйста, внимательно, на что отвечаете, и отвечайте по существу, а не собственным мыслям по поводу того, что написал тот, кому отвечаете:
                                      • Я говорил об ошибке в архитектуре, а не в реализации (ошибки в реализации относительно легко обнаружить в ходе тестирования, особенно при существовании других реализаций)
                                      • Я ничего не говорил о хакерах и других любителях и профессионалах искать коллизии кроме отсутствия их в гипотетической Параллельной Вселенной

                                      P.S. Ещё можно здесь почитать
                              –1
                              Если вы используете криптохеш, то не только можно, но даже нужно (хотя я бы взять уже sha256, а не sha1).

                              Причина очень проста: с некоторой вероятностью ваш компьютер будет считать ненулевой блок нулевым и наоборотнезависимо от того, что и как вы там делаете. И эта вероятность заведомо больше, чем вероятность хеш-коллизий для криптохешей. Ну а наворачивая проверки — вы лишь делаете хуже. Ибо больше мест для сбоя и больше вероятность сбоя.
                            +1
                            Какая тема интересная. А какие программы в Windows поддерживают создание sparse файлов?
                            Кстати, насколько я понимаю файл на скриншоте может быть не только sparse, но и reparse файлом, которые создаются windows dedupe.
                              0
                              Чтение и запись в файлы с установленным sparse флагом может делать любая программа. Установить sparse флаг можно при помощи fsutil. Некоторые торрент клиенты умеют устанавливать sparse флаг самостоятельно.

                              Reparse это как я понимаю про замену идентиных фалов на один с несколькими жескими ссылками на него. Это уже другая тема.
                                0
                                Установить sparse флаг можно при помощи fsutil.

                                только, кажется, после первой записи файла во все эти байты, если у этогой файла даже появятся нулевые блоки – сжатия е произодет. Нужно будет с этого файла снять флаг sparse и поставить его обратно, чтобы произошол повторный анализ файл и его сжатие. Кажется так.
                                Но с таким гемороем, наверно, проще установить какую-нибудь прогу-драйвер, которая создает раздел или типа того, и при записи в который вся инфа будет сжиматься как-будто проходит через архиватор.
                                  0

                                  Флаг необходимо установить на файл пока он нулевого размера. Далее его размер на диске будет зависеть от того сколько данных в него записано.


                                  только, кажется, после первой записи файла во все эти байты, если у этогой файла даже появятся нулевые блоки – сжатия е произодет.

                                  В участки где обнаружены нуль блоки просто не производится запись. Прграмма должна их просто пропустить. Производится только чтение для проверки соответствия хеша.


                                  Нужно будет с этого файла снять флаг sparse и поставить его обратно, чтобы произошол повторный анализ файл и его сжатие.

                                  При снятии флага пустые(не записанные) участки заполнятся нулями. При повторной установке эти нули так и остануться. Но есть утилиты которые прореживают участки которые заполнены нулями.


                                  Также можно проредить заданные участки файла при помоши fsutil.

                                    0
                                    Флаг необходимо установить на файл пока он нулевого размера

                                    Ну да. Не совсем понятно выразился. Фраза «после первой записи файла во все эти байты» означала создание разреженного файла.
                                    В участки где обнаружены нуль блоки просто не производится запись. Прграмма должна их просто пропустить. Производится только чтение для проверки соответствия хеша

                                    Разве? Т.е. создали разреженный файл ➜ записали полностью ➜ и еще раз поверх записали. Разве во время повторной записи будет сжатие?
                                    При снятии флага пустые(не записанные) участки заполнятся нулями. При повторной установке эти нули так и остануться. Но есть утилиты которые прореживают участки которые заполнены нулями.

                                    Также можно проредить заданные участки файла при помоши fsutil.

                                    Точно. Забыл просто как это делается. У меня для этого случая просто батник валяется. Я в его содержимое давно не заглядывал ;)
                              0
                              Интересно бы увидеть статистику из повседневной жизни, какой объем переданных данных сэкономлен, чтобы понять есть ли проблема. Имхо проще качать нули если они есть, чем усложнять + про коллизии выше написали ко всему.
                                0
                                Я их периодически вижу. Оригинальная Shareaza имеет функцию проверить файл полностью при наличии списка хешей. После проверки часто там где все соседние пиры показывали пустой участок Shareaza обнаруживала нуль блоки. Я довольно давно хотел сделать чтобы она их обнаруживала автоматически и запилил эту фукцию у себя.

                                Теперь когда я вижу нуль блоки в файле то сбрасываю его загрузку. Я предпочитаю думать что там действительно нули и файл битый чем то что мне повезло и я созерцаю коллизию. Не может так часто и крупно (бывает больше половины файла) везти.

                                Но можно не сбрасывать и Shareaza скачает только ту часть где есть данные. Тогда найдя полный файл по имени и размеру его можно слить с уже загруженными частями и продолжить загрузку полного файла.

                                Так что это больше не экономия а борьба с битыми файлами.
                                –11

                                Просто атас.


                                Потому что "нуль-блок" пишется через дефис.


                                Извините, но не могу в личку, если ошибка в тексте сразу же в самом-самом старте.

                                  +4
                                  Спасибо. Поправил.
                                    –5

                                    Тогда давайте окончательно дооформляем первое предложение:


                                    1. Про нуль-блоки разобрались, хотя при введении термина хорошо бы его оформить в кавычки "для указания границ".
                                    2. Пропущен пробел перед открывающей скобкой.
                                    3. Пропущена запятая перед "заполненные".

                                    С запятыми вообще вопрос: почему вы их так не любите? :)

                                      +2
                                      У меня есть новость, которая может вас заинтересовать: Отправка сообщений об опечатках в публикациях.
                                        –2
                                        Знаете, а я ведь ждал именно этого коммента, спасибо!

                                        Теперь по пунктам:

                                        1) Если вы посмотрите на приведённый мною скриншот, то увидите там ситуацию с грамотностью, по факту полностью соответствующую крылатой фразе из фильма «О чём говорят мужчины»: «Это не кризис, это — ...».

                                        2) Если вы попробуете найти много запятых в приведённом тексте…

                                        3) Всё это — не есть гут, а есть очень, блин, неграмотно. И сначала все забивают на грамотность, а потом начинают жаловаться, что качество всего и везде как-то падает, да.

                                        4) В упомянутой вами статье особо оговаривается, что функция не работает для мобильной версии. И так уж сложилось, что от 95% до 99% моей активности на сайте происходит через мобильный телефон в состоянии «на ходу». Не подскажете, где у меня можно найти необходимую комбинацию клавиш? ;)

                                        5) Не особо важно, но всё-таки. Если вы внимательно посмотрите на первый комментарий к вашей ссылке… :)
                                          0
                                          5) Не признал :)
                                          4) Не поспоришь. Учитывая ваше участие в профильной дискуссии, будем надеяться, что разработчики учтут эту проблему.
                                          1-3) Тем не менее статью я считаю интересной и проработанной в техническом плане. А с грамотностью видимо необходимо немного (или много) помочь автору.
                                        0
                                        Нельзя ли сделать картинку чуть крупнее? Если смотреть хабр в масштабе 50%, то под вашим комментарием ещё остаётся свободное место, что раздражает.
                                          –1
                                          Это был самый лучший размер, который можно достичь на мобильной версии (см. п.4 выше).

                                          Была бы возможность сделать ещё крупнее — сразу бы удовлетворил пожелания визуально требовательных собеседников!
                                          +1
                                          Спасибо за правки. Исправил. Если слова мне хоть как то помечает Firefox то про запятые он не в курсе. А мысль изложить хочется.
                                      0
                                      Из статьи мне понятно, что нуль-блоки — это вполне обычное явление на сегодня, но их существование нежелательно, если пользователь дорожит свободным местом на своих носителях.
                                      Однако мне трудно определить масштаб этого явления. Иначе говоря, какой может быть относительная доля нуль-блоков в абстрактном носителе на 500Гб?

                                      Отдельно отмечу, что не считаю предмет вашей статьи чем-то бесполезным, но серьёзность проблемы представлена довольно мутно.
                                        0

                                        Наличие нуль-блоков может быть признаком битого файла. Но если для формата их наличие нормально то мы сэкономим немного места и времени не скачивая и не храня их.


                                        Допустим на этот 500ГБ носитель загружается один файл такого же размера. Какой нибудь фильм в UltraMegaHD 4D качестве. И у него всего один нуль-блок. Сколько он будет занимать?


                                        1. В сети Edonkey2000 это фиксировано 9 728 000 байт.


                                        2. В сети BitTorrent файл делится на от 1000 до 1500 блоков. Один нуль-блок в данном случае займёт 512МБ.
                                          536870912000 байт / 1500 блоков = 357913941 байт/блок (341МБ)
                                          Округляем до степени двух в большую сторону: 536870912 байт/блок (512МБ)


                                        3. В сетях где используется Tree Tiger Hash максимально файл делится на 512 частей. Один нуль-блок в данном случае займёт 1ГБ.
                                          536870912000 байт / 512 блоков = 1048576000 байт/блок (1000МБ)
                                          Округляем до степени двух в большую сторону: 1073741824 байт/блок (1ГБ)


                                          0
                                          Вы странно как то считаете, для передачи по сети используется сжатие, в файловых системах тоже есть с эта опция.
                                          Например для передачи по сети 1 гигабайта нулей сколько нужно байт?
                                          Максимально необходимо всего 5 байт, а в хороших упаковщиках размер данных будет на-амного меньше.
                                          На диске нули нужны в программах например для выравнивания данных, для более быстрой обработки и тд. и тп.
                                          У Вас хороший настрой подвергать сомнению, то что есть.
                                          Но нужно копнуть чуть больше.
                                          Как говорили предки? Аз-Буки-Веди.
                                          Пойми Азы-причину Букв-знаков и будешь Ведать-знать.
                                          Копнули бы чуть глубже, сами разобрались бы в причинах и методах решения «нулевых данных».
                                            0
                                            В Bittorent, Edonkey2000, DirectConnect, Gnutella и Gnutella2 сжатие при передаче данных файла не используется.

                                            Я же и призываю использовать механизмы которые предоставляет операционная и файловая система. Прореженные(sparse) файлы это один из них. Он эффективен именно для участков заполненными нулями. Операционная система при чтении программой прореженных участков файла генерирует нули не обращаясь к диску.

                                            При сжатии операционной системе приходится обращаться к диску для чтения инструкций по распаковке каждого блока.
                                              0
                                              Откройте для себя самое простое RLE-сжатие, оно намного эффективнее вашего решения.
                                              То что выше пакет программ не использует сжатие, для передачи, не фатально.
                                              Конечно, самым оптимальным образом нужно подобрать кодек под данные, но если данные «заполнены нулями» и программы эти данные не сжимают их сжимает операционная система, а потом пытается их сжать передающая «железяка», так что решение уже есть и используются довольно давно.
                                              PS:
                                              Если захотите со мной пообщаться напишите в личку, причину «лички» думаю поймете.
                                                0
                                                > Откройте для себя самое простое RLE-сжатие, оно намного эффективнее вашего решения.

                                                В своём клиенте я допустим могу включить сжатие передаваемых данных. Но его должна поддерживать и другая сторона. Для этого надо писать предложение к каждому протоколу и добиться внедрения хотябы в одном популярном в этой сети клиенте.

                                                Списки хешей с другой стороны передают практически все p2p клиенты уже сейчас. И на онове их мой клиент может понять где в файле нуль-блоки и вообще не запрашивать их. По моему не передавать ничего гораздо эффективней чем передавать что то сжатое.

                                                > а потом пытается их сжать передающая «железяка»

                                                То что на железном уровне при передаче есть какое то сжатие не знал. Надо будет по эксперементировать.
                                        0
                                        Во-первых пустые блоки бывают и во вполне нормальных (не повреждённых) файлах, так что считать признаком повреждения их можно только с дополнительными какими-то условиями.

                                        Во-вторых, уже не касательно вашего подхода (хоть он и вызывает опасения из-за возможных коллизий, но вероятность их и правда мала), а касательно самих p2p-протоколов: надёжнее и проще было бы пустые блоки помечать таковыми в таблице хешей сразу, флажком в явном виде, но этого как я понимаю там нигде нет, но если уж речь про доработку клиентов то наверно можно сделать опциональную фичу такую в них, а со временем её и другие начнут поддерживать. И ещё — неужели там сжатия нет? если есть, то качать бы не пришлось особо.
                                          0
                                          Во-первых пустые блоки бывают и во вполне нормальных (не повреждённых) файлах, так что считать признаком повреждения их можно только с дополнительными какими-то условиями.

                                          Согласен. В двух дистрибутивах Ubuntu (1, 2) наблюдаю по одному нуль-блоку. Не будут же они публиковать битый образ диска. В этом случае мы просто экономим по 1МБ дискового пространства и не ждём пока нам раздадут этот нуль-блок.


                                          С другой стороны у сжатых файлов(видео, аудио, архивы) нуль-блоки признак битого файла. Но решает отменить загрузку или нет пользователь. Программа отображает наличие нуль-блоков и качает остальные блоки до отмены загрузки файла.


                                          надёжнее и проще было бы пустые блоки помечать таковыми в таблице хешей сразу

                                          Да флаг + хеш был бы возможно надёжнее. Но это потребует обновления множества клиентов чтоб те отдавали дополнительный флаг.


                                          И ещё — неужели там сжатия нет? если есть, то качать бы не пришлось особо.

                                          Сжатия нет насколько я знаю. Может потому что в основном идёт обмен уже сжатыми данными (архивы, видео, музыка и т.д.) об этом и не задумывались.

                                          0
                                          У вас есть собственная версия Shareaza? Расскажите, очень интересно!
                                          В коде каких еще p2p приложений вы разбирались? retroshare, i2p, freenet, gnunet, tox...? Это чрезвычайно интересная тема!
                                            0

                                            Если известно что размер блока — степень двойки, то показатель степени можно найти по формуле __popcnt(m_nBlockSize - 1)

                                              0

                                              и всё же неспокойно.
                                              sha1 это блок 160 бит, sha 256 — соответственно 256
                                              для блока в 512 мб (2^32 бит) это означает, что каждому значению хеша (включая нулевой) соответствует, ни много ни мало, а примерно 2^24 возможных исходных блоков.
                                              Конечно же, блоков с "ненулевым" хешем гораздо больше — их чуть меньше 2^32 8-)
                                              Но если мы говорим про некий "запакованный" объект — то там степень разнообразия данных выше, и кмк коллизии с нулевым хешем гораздо более реальны.
                                              Вот идея сливать сначала не весь такой объект, а только его часть — кмк может "прокатить": согласно условиям разработки хеша похожие блоки должны иметь существенно различный хеш.

                                                0
                                                Рекомендую почитать какую-нибудь книжку про окончен. Возможно научитесь отличать абсолютную вероятность от относительной. Беспричинная боязнь маленьких вероятностей должна отступить…

                                                Вот это вот откуда, блин:
                                                Но если мы говорим про некий «запакованный» объект — то там степень разнообразия данных выше, и кмк коллизии с нулевым хешем гораздо более реальны.
                                                Разница между этими величинами — одна из важных характеристик крипохеша, а SHA1, при всей его устарелости, всё-таки криптохеш…
                                                  0
                                                  Нуэ. А что посоветуете?

                                                  Я вот понимаю криптографичность кеша как то, что а) нет перекоса в вероятности получить данный хеш (т.е. каждому хешу соответствует примерно одно и то же количество исходных текстов заданной длины), и б) малое изменение исходного текста сильно меняет хеш.

                                                  А про боязнь малых вероятностей — это не совсем так 8-)
                                                  Я не боюсь малой (1/2^256) вероятности получить хеш, который соответствует блоку из нулей. Я боюсь огромной (1-1/2^24) вероятности того, что блок из которого я получил «нулевой» хеш — на самом деле сильно от «нулевого блока» отличается. Особенно если у нас сильно меняется распределение вероятностей засчет некого изменения исходных данных («сжатие»).

                                                  PS. Я как-то в детстве читал что-то типа «занимательной математики». Там был рассказ про доцента и профессора, которые поспорили на велосипед, что за 10 минут в выходной день в маленьком городке мимо окна не пройдёт 100 человек. Доцент утверждал, что вероятность этого абсолютно, ничтожно мала — и тут мимо прошел отряд военных.
                                                  Может, кто знает, что это была за книга?
                                                    0
                                                    Нуэ. А что посоветуете?
                                                    Судя по вашим высказываниям нужно с самого начала начинать. С какой-нибудь занимательной статистики в комиксах.

                                                    Я боюсь огромной (1-1/2^24) вероятности того, что блок из которого я получил «нулевой» хеш — на самом деле сильно от «нулевого блока» отличается.
                                                    Может быть тогда вы сможете понять — в каком месте вы сделали ошибку и из какого… гхм… места вытащили свою «огромную» вероятность.

                                                    Потому что пока я даже представить не могу что вы считали и как что у вас такая вероятность получилась.

                                                    P.S. Чисто для справки: каждому значению хеша (влючая нулевой) соотвествует не «примерно 2^24 возможных исходных блоков», а порядка 2232-160 исходных блоков. Это число — столь велико, что если его тут взять и записать — у вас браузер повиснет. Но это не меняет того факта, что ваша ультраогромная вероятность таки равна 2-160. И будет равна ровно этому независимо от размера блока (за исключением блоков с длиной сильно близкой к длине хеша: если у вас есть, скажем, всего 161 бит, то не факт, что там вероятности будут равны).

                                                    P.P.S. То, что вы историю из Перельмана вспомнили — это прекрасно, но тут хорошо бы всё-таки не только про смешные рассказы помнить…
                                                      0
                                                      Окей. Попробуем начать с основ статистики.
                                                      Да и с подсчётом я облажался. N бит представляют 2^N различных блоков, и тогда 512 мб это 2^32 бит, и соответственно 2^(2^32) различных блоков, и на одно значение хеша приходится, как вы и сказали, 2^(2^32-160) различных блоков.

                                                      Но только вот какая штука:
                                                      Если нам дали значение хеша, и мы генерируем некий блок данных, то мы получим именно тот хеш, который нам дали с вероятностью 2^-160. Ок.
                                                      Но если значение хеша, которое нам дали, внезапно совпало с хешем блока, который мы вот только что сгенерили (т.е. наша вероятность коллизии 2^-160 уже сработала) — то вероятность того, что «на той стороне» посчитали хеш именно из этого блока — 2^-(2^32-160), если у нас нет каких-либо предположений о распределении данных «на той стороне».

                                                      Собственно, это должно быть свойством криптохеша — см. п.3 для свойств идеального криптохеша:
                                                      3. Невозможность сгенерировать сообщение из его хеш-значения, за исключением попыток создания всех возможных сообщений


                                                      Ну и в рамках данного обсуждения мы «сгенерили» блок из всех нулей, что на вышеизложенные размышления влиять не должно.

                                                      Буду рад, если мне укажут на ошибку в моих предположениях.
                                                      Спасибо.

                                                      PS. И за Перельмана отдельное спасибо. 8-)
                                                        0
                                                        Читать книжку по статистике. В частности про условные вероятности. То, что у вас случится после того, как вы обнаружите коллизию — мало кому интересно, так как всё равно вы с вероятностью 1-2-160 этого никогда не увидите — а так как эта вероятность существенно превышает вероятность того, что наша цивилизация вот прямо завтра «кончится» из-за падаения астероида, то и обсуждать всё это большого смысла не имеет.
                                                +1
                                                Все равно в основе магнет ссылок и прочего p2p просто хеши. Такие же по алгоритму, как и для частей файлов. И проверка идет по хешам. Значит, если мы считаем вероятность коллизии значимой, то просто нельзя пользоваться пирингом. Нет?
                                                  –1
                                                  Если бы тут кто-то хотел найти истину, то ваше рассуждение было бы логично. Но, увы, после «возврата» гиктаймс подавляющему большинству истина на Хабре не интересна…
                                                  0
                                                  Немного offtop:
                                                  Не хватает в Transmission на NAS выключение переиндексации (вычисления хешей) для ранее скаченных файлов, например, добавляется новая серия в раздачу, приходится ждать пока для всех серий не подсчитаются хеши и только потом начинается скачивание.
                                                    0
                                                    Ждём статью «хватит качать единицы», об аналогичных блоках из единиц. А потом финальную статью, «о пользе архиваторов».
                                                      0
                                                      Разве торрент не поддерживает сжатие данных на лету? Что-то мне подсказывает, что 16 Мб нулей при сжатии gzip превратятся в те-же самые 4 Кб.
                                                        0
                                                        Какое простое решение проблемы! Или вообще сжать файлы ещё на стадии раздачи, до передачи. Никаких вам нулей, и всё быстро-компактно
                                                        0

                                                        Интересная статья. Что заинтересовало, почему Lua 5.1 в 2019 году? 5.3 вполне себе живёт и процветает.


                                                        Если проект старый и большой, то там всё ясно: обновление с 5.1 на более свежую версию с большой долей вероятности боль. Но в чистом проекте почему не 5.3?

                                                          0
                                                          Можно поменять на версию 5.3. Единственная косметическая проблема это появление нуля с точкой:
                                                          ```
                                                          // tth_hashes
                                                          // Hash: 13143C45D95485EACD9C47D72630EF0139436CB77DF2632B Size: 1024.0
                                                          // Hash: 855DCE7FE3E963F50295A673120E6259165CED9F086DB031 Size: 2048.0
                                                          // Hash: 38FB763B44ECA3B13F40182C75694360AC8DA0865DDB29D6 Size: 4096.0
                                                          // Hash: 721BEF53CBBDA47BE44BD26C43EC048F136D371E918200CF Size: 8192.0
                                                          // Hash: AFDDF505C1E1D5AF8FAE007BBE4E64578F34D912345E23D8 Size: 16384.0
                                                          // Hash: 53CC478ED14FF7FB671F94ECE0FD7C8C5DCB2FE611ACAC6B Size: 32768.0
                                                          ```
                                                            0

                                                            Quick-and-dirty решается приведением к инту (если не ошибаюсь, math.tointeger(x)), хотя как он вышел дробным — не могу понять сходу.

                                                              0

                                                              Вот проблемная строка:


                                                              print("// Hash: "..hash_hex, " Size: "..(1024*2^i));

                                                              Решил проблему при помощи math.floor:


                                                              print("// Hash: "..hash_hex, " Size: "..math.floor(1024*2^i));

                                                              Эта функция присутствует и до версии 5.3.

                                                                0
                                                                Самому вот интересно теперь стало, почему целое в целой степени оказывается дробным.
                                                            0
                                                            А почему там должно быть 5.3?
                                                            Да хоть 1.0 (не в курсе, есть ли такая) — если она свою задачу выполняет и при этом не содержит дыр, то всё в порядке.
                                                              0
                                                              1.0 существует, но она ну совсем непохожа на 5.x.
                                                              Просто есть некоторые проблемы переносимости между 5.1/5.3, так почему бы и не юзать 5.3 в новом проекте?
                                                            0
                                                            Не хватает очень многого… подсчёта хеш сумм и дедупликация трафика, прогрессивный стриминг с кешированием и нормальные плеера под все ОС.

                                                            Но с нулями у нормальных людей проблем нет.
                                                              +2
                                                              Можно написать вторую часть статьи «хватить качать единицы!», и изобрести архивацию(компрессию).
                                                                0

                                                                Вы уже не первый человек со схожими мыслями. У меня есть расширенная версия скрипта которая вычисляет хеши различных шаблонов. Также я хотел реализовать дедубликацию блоков. Но это уже менее приоритетные вещи.


                                                                А детектор нуль-блоков эффективно помогает мне не качать "битые" блоки файла и решить стоит ли этот файл вообще качать при их наличии.

                                                              Only users with full accounts can post comments. Log in, please.