PRL加密方案在广告投放中的应用

1.背景

1.1为什么要加密

广告生态中，数据安全合规越来越重要，在保证用户安全隐私基础上，再开展广告业务是业内的共识。现阶段在广告投放流程中的RTA（Real-Time API）环节，请求参数中的设备号是以MD5的形式进行交互。MD5又被称为单向散列函数，虽然具有不可逆性（根据 MD5 值计算不出原始数据）及唯一性（不同原始数据会有不同的 MD5 值，碰撞率极低）特点，但还是存在一定被破解的风险，比如暴力穷举、彩虹表法、差分攻击，这就给个人隐私保护带来一定的挑战。

为了进一步保障个人信息安全，字节为广告主提供了PRL加密方案。PRL概念早在2004年就曾出现于数据挖掘的权威论文中，该论文至今已获得230多次引用，足以证明业界对PRL效果的认可，并且优势突出：开源、安全、可扩展，此方案可以保证媒体和广告主双方的信息安全，套用一句我们产品大大的话：采用PRL加密后，你只认识你认识的人。

1.2PRL加密简介

• 定义：PRL（Private Record Linkage）是隐私保护的记录链接（也称为Privacy-Preserving Record Linkage）。

• 目标：保证生态链路数据安全，广告主可以拿到与媒体测的交集数据，用于后续投放识别。

• 主要流程：

• 输入加盲DID；

• 巨量引擎返回哈希加密巨量引擎ID；

• 广告主将哈希加密巨量引擎ID去盲，并记录DID与加密巨量引擎ID的映射关系。

• 技术原理：利用了非对称加密的ECC方案（椭圆曲线密码学），是一种基于椭圆曲线数学的公开密钥加密方案，其优势在于使用较小的密钥长度并提供相当等级的安全性，一般认为160位密钥的ECC安全性相当于1024位密钥的RSA，256位相当于3072位（目前普遍使用的RSA密钥长度是2048位）。

• PRL相关论文：

  Private Record Linkage：https://link.springer.com/content/pdf/10.1007/978-3-319-34129-3_36.pdf

  Privacy-Preserving Record Linkage：https://www.cs.cmu.edu/~rjhall/linkage_survey_final.pdf

2.加密方案

整个加密方案分为离线求交和在线投放两部分。离线求交是为在线投放做前置准备工作，拿到字节加密的设备号与广告主所拥有的设备号进行映射关系存储。

2.1离线求交

1. 广告主将自己存量的设备号进行加盲，传输给巨量引擎

2. 巨量引擎对收到的加盲数据用私钥加密，将加密的结果回传给广告主

3. 广告主对收到的加密加盲数据用公钥去盲，并记录媒体加密的设备号与原始设备号的映射关系

2.2在线投放

1. 广告请求发生，巨量引擎对设备ID进行加密

2. 广告主接受加密ID，查询匹配获得真实DID

3. 后续投放流程正常执行

3.方案实现

3.1方案调研

首先，我们对现有存量和增量设备号进行了统计。存量设备号分为这几个部分，人群包、曝光数据和RTA请求的数据，总数据量达到了数百亿级别。增量设备号主要是每天的RTA请求及曝光数据，这部分每天的增量去重后也有数千万，然后根据预估的数据量级进行加密及映射关系处理。

考虑到RTA对请求响应时间的严苛要求，而且数百亿数据确实不是个小数目，所以这些设备号的映射关系最好不要存到mysql这种关系型数据库中，一来耗费巨大的存储空间（TB级别），二是因为RTA的请求量巨大（目前达到了几十万qps），每个请求都要去数据库中查它的映射值，这会导致mysql压力巨大，响应时间也不能得到很好的保证。综合来看，我们最终采用了redis存储的方案。

存量数据：主要的RTA请求和曝光数据这两部分就有百亿级别的数据，经过与我司大数据团队进行协作，将数据分为数百个分区存入hive中，然后应用代码通过jdbc的方式进行读取和处理。

增量数据：主要就是RTA请求的增量设备号，因历史老的请求和头条穿山甲RTA存在未加密的设备号，这部分设备号还是需要进行加密映射的。经过计算，每小时的设备号有数亿（未去重，去重完只剩百万级别数据量），这部分数据量着实不小，所以必须得进行去重。考虑到百亿级别数据去重的主流方案，我们最终用到了布隆过滤器，每个请求会先去布隆过滤器中查，查不到的话才去调字节加密接口，这样大大减少了重复的请求。

存储结构我们采用redis的hash ziplist，将数百亿设备号分为1亿个bucket，每个bucket存放一定数量的hashkey（小于512，ziplist数据结构要求），hash value为我们自己的设备号，进行设备号映射关系的存储，预估大约占用空间1.7T左右。

3.2技术实现

RTA请求加密接口文档：https://bytedance.feishu.cn/docs/doccnM8He6BvgBhjIiHyXadcXzh

GitHub地址：https://github.com/volcengine/SecureUnionID

字节为PRL加密方案提供了整个加密流程的sdk，获取加密设备号只需调用字节的接口就行，不过前期的加盲及后续的去盲及验证需要我们自己去实现。据字节技术文档介绍，请求响应采用了proto进行序列化（体积更小，传输更快），性能方面，同时传输1w个did进行加密，接口耗时约300ms，qps约10w。

首先可以一起看下字节提供的加密Demo，梳理加密步骤流程如下：

这里有两个公钥及一个私钥，均由字节提供。公钥下发给我们，私钥存放在字节侧用于加密需要下发给我们的数据，我们只需要去实现step2、3、5。梳理过程中发现有两个比较麻烦的地方：

1. sdk只提供了go、java、python的源码，需要自己将此sdk打成jar包传到私服，然后pom中引入其坐标进行api调用，或直接导入本地jar包至项目工程代码中。

2. Demo中对于生成system key、加盲、去盲、验证这几点是用C语言去实现的，要成功调用这些api，得先将由C语言写的源码编译成对应系统下的动态链接库（Windows下为.dll文件，Linux下为.so文件），然后java的话通过JNI进行调用。

3.2.1生成动态链接库

Windows环境：

• mingw（可以理解为Windows下的gcc）

• Clion（C/C++的IDE）

• jdk1.8及以上

环境准备好后，将sdk的java版本源码导入Clion中，配置ToolChains（mingw的安装地址），然后编译，便得到了Windows下的.dll文件：libsecureunionidjni-win64.dll。

Linux环境：

• Cmake

• make

• gcc

• jdk1.8及以上（注意配置JAVA_HOME）

• openssl

关于gcc、make和CMake的区别：https://www.cnblogs.com/xuelisheng/p/9988626.html

安装好如上环境后，将源码导入Linux环境中，执行以下命令便可以得到Linux下的.so文件：libsecureunionidjni-linux64.so

$ cmake -DCMAKE_BUILD_TYPE=Release ..

$ make

3.2.2打成jar包上传私服

将sdk源码导入IDEA中，然后将.dll文件和.so文件拷贝到项目resources下，用maven进行打包，这样便生成了sdk对应的jar包。

执行以下命令将jar包上传到公司私服：

mvn deploy:deploy-file -Dmaven.test.skip=true -Dfile=secureunionid-0.2.jar -DgroupId=com.xxx.rta-encryption -DartifactId=secureunionid -Dversion=0.2 -Dpackaging=jar -DrepositoryId=releases -Durl=http://maven.repo.xxx.com/nexus/content/repositories/releases/

至此，我们便可以在项目中引入对于的pom坐标，调用加密相关api了。

<dependency>
    <groupId>com.xxx.rta-encryption</groupId>
    <artifactId>secureunionid</artifactId>
    <version>0.2</version>
</dependency>

3.2.3存量设备号加密

先看下加密接口protobuf文件：

package adx.psi;

enum ResponseCode {
	// 签名成功
	Success = 0; 
    // sender与outId不匹配, 认证失败
    SenderOutIdMatchFailed = 100;
	// 未找到广告主对应的的私钥
	SkAuthenticationFailed = 101;
	// 触达最大访问量, 广告主应尽量将did与加密did落库
	ThresholdReached = 102;
    // server签名算法抛出异常
    InnerAlgorithmFailed = 103;
}

message SignRequest {
	// 发起签名的一方,能够标示广告主的Identity, 媒体侧需要这个参数找到广告主对应的私钥
    required string sender = 1;
    // 广告主和对应媒体约定的outId
    required string out_id = 2;
    // 广告主需要媒体签名的数据，这部分数据广告主已经盲化过
    repeated string blinded_messages = 3;
}

message SignResponse {
	// 标记媒体侧的Identity，方便广告主做正确性校验以及定位出有问题的媒体
    required string receiver = 1;
    // 媒体返回的状态码
    required ResponseCode rsp_code = 2;
    // 媒体基于当前receiver所使用密钥的版本
    required string sk_version = 3;
    // 媒体私钥签名后的数据，顺序与输入数据对齐。
    repeated string signed_messages = 4;
}

请求参数中的sender和outId由字节提供，blinded_messages为加盲过的设备号。job流程如下：

• 数据库取1w条设备号

• 加盲加密

• 存入redis，key为加密设备号的CRC32模1亿，hashkey为加密设备号的高八个字节转整型，hashvalue即为我们自己的设备号

采用OkHttp进行protobuf接口请求：

public static AdxPsiProto.SignResponse postProto(String url, AdxPsiProto.SignRequest body) throws IOException {
    RequestBody requestBody = RequestBody.create(MediaType.parse("application/x-protobuf"), body.toByteArray());
    Request request = new Request.Builder().url(url).post(requestBody).build();
    OkHttpClient client = new OkHttpClient();
    ResponseBody responseBody = client.newCall(request).execute().body();
    if (responseBody == null) {
        return null;
    }
    return AdxPsiProto.SignResponse.parseFrom(responseBody.byteStream());
}

将设备号映射关系写入redis

public void setEncryption(String key, String value) {
    long slot = CRC32Util.getCRC32Value(key) % 1亿;
    long numKey = UUIDUtil.uidLong(key);
    redisService.setEncryption(slot + "", numKey + "", value);
}

因为存量设备号由三部分构成，为了便于控制，我们新增三个定时任务进行处理。同时由于数据量巨大，采用了多线程进行处理。但由于加盲，去盲和验证特别耗CPU资源（PRL加密方案导致）。经过测试，一台2C4G的机器处理1w条数据约耗费12分钟，如果开25个线程（此时已经将CPU负载打满），一台机器一天只能处理3000w的数据，现在存量数百亿的数据得八百多天，整个时间实在是太久了。由于业务期望两周内将此功能上线，我们就按14天去处理数据，机器配置替换成了4C8G，1w条数据处理时间由12分钟降到5分钟左右，这样每台机器开25个线程每小时约可以处理8000w的数据，同时又申请了20台机器并行处理，这样所有的数据差不多两周左右可以处理完。

3.2.4增量设备号加密

对于增量设备号这部分，人群包、曝光数据这三部分可以调整job执行时间对增量数据进行定时处理。比如目前生产对于曝光的数据每小时会去查询最近1小时的数据进行加密映射处理。

而对于RTA请求的这部分数据，我们先将存量的设备号写入布隆过滤器中，然后所有RTA请求的设备号先查询布隆过滤器，若不在则批量或者定时进行加密处理，若存在则不处理，下面简单介绍下布隆过滤器。

• **概念：**布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

• **原理：**当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点（offset），把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。一句话解释：不存在的一定不存在，存在的不一定存在。

• **redis实现：**redis数据结构中bitmap就可以很好的实现布隆过滤器，可以把bitmap想象成一个以位为单位数组，数组中的每个单元只能存0或者1，数组的下标在bitmaps中叫做偏移量。其中有一点要注意，单个bitmap的最大长度是512MB，即2^32个比特位，约42亿多，所以对于我们数百亿级别的数据无法用单个bitmap去实现，这里我们用了50个bitmap，每个布隆的key为：deviceIdBloomKey: + 加密设备号的CRC32值对50取模，每个布隆负责10亿个设备号的去重，整个布隆过滤器约占用redis空间约为12GB。

核心类

@Component
public class RedisBloomFilter<T> {
    @Autowired
    @Qualifier("EncryptionRedisTemplate")
    private RedisTemplate<String, String> redisTemplate;

    /**
     * 根据给定的布隆过滤器添加值
     */
    public <T> void addByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            redisTemplate.opsForValue().setBit(key, i, true);
        }
    }

    /**
     * 根据给定的布隆过滤器判断值是否存在
     */
    public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
        Preconditions.checkArgument(bloomFilterHelper != null, "bloomFilterHelper不能为空");
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            if (!redisTemplate.opsForValue().getBit(key, i)) {
                return false;
            }
        }
        return true;
    }
}

封装的工具类

bit数组长度和hash方法执行次数这两个值的最优解都有公式进行计算，这里有两个参数需要注意下，它们直接决定了布隆的大小：

• expectedInsertions：这个代表了预计会插入多少数据到布隆过滤器里，比如这次是10亿（因为用了50个bitmap）

• fpp：误差率，因为布隆是无法100%确定数据存在的，误差率越小，所占用的空间就越大，因为这次我们只需要判断数据不在布隆过滤器中，设置0.01就够用

@Configurable
public class BloomFilterHelper<T> {
    private int numHashFunctions;
    private int bitSize;
    private Funnel<T> funnel;

    public BloomFilterHelper(Funnel<T> funnel, long expectedInsertions, double fpp) {
        Preconditions.checkArgument(funnel != null, "funnel不能为空");
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    public int[] murmurHashOffset(T value) {
        int[] offset = new int[numHashFunctions];

        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitSize;
        }
        return offset;
    }

    /**
     * 计算bit数组长度
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 计算hash方法执行次数
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

3.2.5业务流程改造

待所有数据准备好后，在每次RTA请求到达之后，先判断请求媒体是否为抖音，是则拿到字节解密后的设备号查询redis拿到原始设备号，然后将后续流程的设备号都替换为解密后的设备号，这样后续所有流程都无需改造。流程如下：

4.总结

1. 对于映射关系存储这一块，采用redis hash数据结构，将hash key的数量控制在512以内，可以利用ziplist结构减少存储空间的占用。同时key从string类型经过hash转换为long类型，这样空间占用从32字节减少到8个字节，也可以显著降低key空间的占用。

2. 对于布隆过滤器这一块，如果采用redis去实现，特别需要注意bitmap数据结构底层也是string，因为redis 限制了字符串最大长度不得超过 512M，所以最大存储的数据范围为2^32，约42亿多，对于多到百亿数据的去重可以考虑使用多个布隆过滤器。

3. 字节加密的sdk特别耗CPU性能，导致百亿级的数据处理数据要很久，所以前期要做好较为准确的预估，需要什么配置的机器，需要多少台，每台开多少线程，不然等到上线的时候发现问题就可能影响到功能的正常上线了。

5.方案缺点及后续优化

1. 目前对于RTA请求，增量设备号加密的处理是放在RTA的服务器中，因为加密太耗CPU的性能了，导致在处理增量数据加密的时候，服务器的CPU负载会变高，如果处理加密的线程设置多一点会直接导致RTA请求响应时间拉长，目前生产设置的是单线程处理。后续优化方向：请求通过布隆过滤器后，不存在的设备号发送到mq进行异步处理。

2. 而对于曝光的那部分数据，现在每天增量有数亿，对于现在job每小时去定时处理这些数据压力还是蛮大的，而且占用机器资源（目前生产机器配置：数台4C8G）。后续优化方向：在对曝光那部分数据在写数据库的时候就用布隆过滤器过滤出新设备号，然后发送到mq进行异步处理。

招聘信息

Java、大数据、前端、测试等各种技术岗位热招中，欢迎扫码了解~

更多福利请关注官方订阅号“拍码场”

好内容不要独享！快告诉小伙伴们吧！

喜欢请点击↓↓↓